perm filename V231.XGP[TEX,DEK] blob sn#540837 filedate 1980-10-13 generic text, type T, neo UTF8
/NOWRAPAROUND/LMAR=50/TMAR=50/RMAR=1700/BMAR=1/PMAR=0/XLINE=0/FONT#0=NGR13/USETI=000000070*TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX*

␈β	[␈↓ α4␈ε"SECTION␈α3.1␈αof␈αTHE␈αAR␈α⎇T␈αOF␈αCOMPUTER␈αPR␈α␈OGRAMMING
␈β
ε␈↓ β'␈ε6⎇␈ε"␈α1980␈αAddison↑W␈α⎇esley␈αPublishing␈αCompan␈α␈y,␈αInc.
␈β⊃H␈↓ ε2␈ε$0
␈β∪(

␈β↓l␈↓ ↓H␈∧↓l↓H↓(␈↓ ¬␈∧↓l¬↓(
␈β↓m␈↓ ↓H␈∧↓m↓H(↓␈↓ ,␈∧↓m,(↓
␈βαI␈↓ ↓H␈ε>C␈α∧H␈α∧A␈α∧PT␈αβE␈α∧R␈α$TH␈α∧R␈αβE␈α∧E
␈ββu␈↓ ¬c␈ε<RAN␈α␈DO␈α↓M␈α1N␈α␈UMBER␈α␈S
␈β¬
␈↓ π'␈ε Any␈α␈one␈αwho␈αconsiders␈αarithmetical
␈β¬1␈↓ π
␈ε methods␈αof␈αproducing␈αrandom␈αdigits
␈β¬Y␈↓ πk␈ε is,␈αof␈αcourse,␈αin␈αa␈αstate␈αof␈αsin.
␈βε→␈↓ π<␈ε?←JOHN␈↓ λF␈ε?V␈α␈ON␈αNEUMANN␈α(1951)
␈βεz␈↓ π∨␈ε Lest␈αmen␈αsuspect␈αy␈α␈our␈αtale␈αuntrue,
␈βπ!␈↓ λ8␈ε Keep␈αprobabilit␈α␈y␈αin␈αview.
␈βπa␈↓ λs␈ε?←JOHN␈↓ 	⎇␈ε?GA␈α⎇Y␈α(1727)
␈βλB␈↓ εf␈ε There␈αw␈α␈anted␈αnot␈αsome␈αbeams␈αof␈αlight
␈βλi␈↓ ∧g␈ε to␈αguide␈αmen␈αin␈αthe␈αexercise␈αof␈αtheir␈αStocastick␈αfacult␈α␈y.
␈β	)␈↓ λN␈ε?←JOHN␈↓ 	X␈ε?O␈α␈WEN␈α(1662)
␈β
a␈↓ ↓H␈ε=3␈α␈.1.␈α∩INTROD␈α␈UC␈α↓T␈α␈I␈α↓O␈α␈N
␈β'␈↓ ↓H␈ε"N␈↓ ββ␈ε"that␈α∂are␈α∞\chosen␈α∂at␈α∞random"␈α∂are␈α∞useful␈α∂in␈α∂man␈α␈y␈α∞di{eren␈α␈t␈α∂kinds␈α∞of
␈β,␈↓ ↓d␈ε.UMB␈α↓ERS
␈βR␈↓ ↓H␈ε"applications.␈α⊂F␈α⎇or␈αexample:
␈β
␈↓ ↓b␈ε"a)␈↓ α␈ε/Sim␈α␈ulation.␈ε"␈α⊃When␈α
a␈α	computer␈α
is␈α
being␈α
used␈α	to␈α
sim␈α␈ulate␈α
natural␈α	phenomena,
␈β8␈↓ ↓H␈ε"random␈αn␈α␈um␈α␈bers␈α
are␈α
required␈αto␈α
mak␈α␈e␈α
things␈αrealistic.␈α∩Sim␈α␈ulation␈α
co␈α␈v␈α␈ers␈αman␈α␈y
␈βc␈↓ ↓H␈ε"|elds,␈αfrom␈α
the␈αstudy␈αof␈α
n␈α␈uclear␈αph␈α␈ysics␈α(where␈α
particles␈αare␈α
subject␈αto␈αrandom
␈β
∞␈↓ ↓H␈ε"collisions)␈α⊂to␈α⊃operations␈α⊃research␈α⊂(where␈α⊃people␈α⊃come␈α⊂in␈α␈to,␈α∩sa␈α␈y,␈α∩an␈α⊃airport␈α⊂at
␈β
:␈↓ ↓H␈ε"random␈αin␈α␈terv␈α}als).
␈β
t␈↓ ↓`␈ε"b)␈↓ α␈ε/Sampling.␈ε"␈α⊂It␈α	is␈α
o$en␈α	impractical␈α
to␈α	examine␈α
all␈α	possible␈α
cases,␈α
but␈α	a␈α	random
␈β∞∨␈↓ ↓H␈ε"sample␈αwill␈αpro␈α␈vide␈αinsigh␈α␈t␈αin␈α␈to␈αwhat␈αconstitutes␈α\t␈α␈ypical"␈αbeha␈α␈vior.
␈β∞Z␈↓ ↓d␈ε"c)␈↓ α␈ε/Numerical␈αanalysis.␈ε"␈α∀Ingenious␈α
techniques␈αfor␈α
solving␈αcomplicated␈α
n␈α␈umerical
␈β∂¬␈↓ ↓H␈ε"problems␈α∂ha␈α␈v␈α␈e␈α∂been␈α∂devised␈α⊂using␈α∂random␈α∂n␈α␈um␈α␈bers.␈α~Sev␈α␈eral␈α∂bo␈α↓oks␈α∂ha␈α␈v␈α␈e␈α∂been
␈β∂1␈↓ ↓H␈ε"written␈αon␈αthis␈αsubject.
␈β∂k␈↓ ↓`␈ε"d)␈↓ α␈ε/Computer␈α∞programming.␈ε"␈α≡Random␈α∞v␈α}alues␈α∂mak␈α␈e␈α∞a␈α∂go␈α↓od␈α∞source␈α∂of␈α∞data␈α∞for
␈β⊂⊗␈↓ ↓H␈ε"testing␈α
the␈αe{ectiv␈α␈eness␈α
of␈αcomputer␈α
algorithms.␈α⊂This␈α
is␈α
the␈αprimary␈α
application
␈β⊂B␈↓ ↓H␈ε"of␈α∂in␈α␈terest␈α⊂to␈α⊂us␈α⊂in␈α∂this␈α⊂series␈α⊂of␈α∂bo␈α↓oks;␈α∩it␈α⊂accoun␈α␈ts␈α⊂for␈α∂the␈α⊂fact␈α⊂that␈α∂random
␈β⊂m␈↓ ↓H␈ε"n␈α␈um␈α␈bers␈α⊃are␈α⊃already␈α⊃being␈α⊃considered␈α⊃here␈α⊃in␈α⊃Chapter␈α⊃3,␈α∩before␈α⊃most␈α⊃of␈α⊃the
␈β⊃_␈↓ ↓H␈ε"other␈αcomputer␈αalgorithms␈αha␈α␈v␈α␈e␈αappeared.
␈β⊃H␈↓ ε2␈ε$1
␈β∪(

␈β↓U␈↓ ↓H␈ε"2␈↓ 
}␈ε"3.1
␈β↓\␈↓ α=␈ε∞RANDOM␈α
NU␈α↓MB␈α␈E␈α↓RS
␈βα"␈↓ ↓d␈ε"e)␈↓ α␈ε/Decision␈αmaking.␈↓ ∧2␈ε"There␈αare␈αreports␈αthat␈α
man␈α␈y␈αexecutiv␈α␈es␈αmak␈α␈e␈αtheir␈αdeci-
␈βαM␈↓ ↓H␈ε"sions␈αby␈α
⎇ipping␈α
a␈αcoin␈α
or␈α
by␈αthro␈α␈wing␈α
darts,␈α
etc.␈α∩It␈α
is␈αalso␈α
rumored␈α
that␈αsome
␈βαy␈↓ ↓H␈ε"college␈α
professors␈α∞prepare␈α∞their␈α
grades␈α∞on␈α
such␈α∞a␈α∞basis.␈α∃Sometimes␈α
it␈α∞is␈α
impor-
␈ββ$␈↓ ↓H␈ε"tan␈α␈t␈α
to␈αmak␈α␈e␈αa␈α
completely␈α\un␈α␈biased"␈αdecision;␈αthis␈α
abilit␈α␈y␈αis␈αoccasionally␈α
useful
␈ββO␈↓ ↓H␈ε"in␈α
computer␈α∞algorithms,␈α
for␈α∞example␈α
in␈α∞situations␈α
where␈α∞a␈α
|xed␈α∞decision␈α
made
␈ββz␈↓ ↓H␈ε"each␈α
time␈αw␈α␈ould␈αcause␈α
the␈αalgorithm␈αto␈α
run␈αmore␈αslo␈α␈wly.␈α∂Randomness␈αis␈αalso␈α
an
␈β∧%␈↓ ↓H␈ε"essen␈α␈tial␈αpart␈αof␈αoptimal␈αstrategies␈αin␈αthe␈αtheory␈αof␈αgames.
␈β∧`␈↓ ↓h␈ε"f)␈↓ α␈ε/Recreation.␈ε"␈α↔Rolling␈↓ ∧T␈ε"dice,␈αsh␈α␈u␈␈ing␈αdecks␈αof␈αcards,␈αspinning␈αroulette␈αwheels,
␈β¬␈↓ ↓H␈ε"etc.,␈α∞are␈α∞fascinating␈α∞pastimes␈α∞for␈α
just␈α∞about␈α∞ev␈α␈erybody.␈α⊗These␈α∞traditional␈α
uses
␈β¬7␈↓ ↓H␈ε"of␈αrandom␈αn␈α␈um␈α␈bers␈α
ha␈α␈v␈α␈e␈αsuggested␈α
the␈αname␈α
\Mon␈α␈te␈αCarlo␈αmethod,"␈α
a␈αgeneral
␈β¬b␈↓ ↓H␈ε"term␈αused␈αto␈αdescribe␈αan␈α␈y␈αalgorithm␈αthat␈αemplo␈α␈ys␈αrandom␈αn␈α␈um␈α␈bers.
␈βε≥␈↓ α␈ε"People␈α
who␈α∞think␈α
about␈α∞this␈α
topic␈α∞almost␈α
in␈α␈v␈α}ariably␈α∞get␈α
in␈α␈to␈α
philosophical
␈βεH␈↓ ↓H␈ε"discussions␈αabout␈α
what␈α
the␈α
w␈α␈ord␈α
\random"␈αmeans.␈α∪In␈αa␈α
sense,␈α
there␈α
is␈α
no␈αsuch
␈βεs␈↓ ↓H␈ε"thing␈αλas␈α	a␈αλrandom␈α	n␈α␈um␈α␈ber;␈α	for␈α	example,␈α	is␈αλ2␈α	a␈αλrandom␈α	n␈α␈um␈α␈ber?␈α∂Rather,␈α	w␈α␈e␈αλspeak
␈βπ∨␈↓ ↓H␈ε"of␈α
a␈↓ α↔␈ε/sequence␈α
of␈α
independen␈α␈t␈α
random␈αn␈α␈um␈α␈bers␈ε"␈α
with␈α
a␈αspeci|ed␈↓ 	&␈ε/distribution␈ε",␈α
and
␈βπJ␈↓ ↓H␈ε"this␈α⊂means␈α⊂lo␈α↓osely␈α⊂that␈α⊃each␈α⊂n␈α␈um␈α␈ber␈α⊂w␈α␈as␈α⊂obtained␈α⊃merely␈α⊂by␈α⊂chance,␈α⊃ha␈α␈ving
␈βπu␈↓ ↓H␈ε"nothing␈αto␈αdo␈αwith␈αother␈α
n␈α␈um␈α␈bers␈αof␈αthe␈αsequence,␈αand␈α
that␈αeach␈αn␈α␈um␈α␈ber␈αhas␈αa
␈βλ ␈↓ ↓H␈ε"speci|ed␈αprobabilit␈α␈y␈αof␈αfalling␈αin␈αan␈α␈y␈αgiv␈α␈en␈αrange␈αof␈αv␈α}alues.
␈βλM␈↓ α␈ε"A␈↓ α.␈ε/uniform␈ε"␈α	distribution␈αλon␈αλa␈α	|nite␈αλset␈αλof␈α	n␈α␈um␈α␈bers␈αλis␈αλone␈αλin␈α	which␈↓ 	d␈ε"each␈αλpossible
␈βλx␈↓ ↓H␈ε"n␈α␈um␈α␈ber␈α	is␈α
equally␈α
probable.␈α∂A␈α	distribution␈α
is␈α
generally␈α	understo␈α↓od␈α
to␈α
be␈α	uniform
␈β	#␈↓ ↓H␈ε"unless␈αsome␈αother␈αdistribution␈αis␈αspeci|cally␈αmen␈α␈tioned.
␈β	K␈↓ λy␈ε%1
␈β	O␈↓ α␈ε"Each␈α⊃of␈α⊂the␈α⊃ten␈α⊂digits␈α⊃0␈α⊂through␈α⊃9␈α⊂will␈α⊃occur␈α⊂about␈↓ 	$␈ε"of␈α⊃the␈α⊂time␈α⊃in␈α⊂a
␈β	`␈↓ λr␈ε%10
␈β	d␈↓ λr␈∧	dλrα∨
␈β	{␈↓ ↓H␈ε"(uniform)␈α
sequence␈α∞of␈α
random␈α
digits.␈α∃Each␈α
pair␈α∞of␈α
t␈α␈w␈α␈o␈α∞successiv␈α␈e␈α
digits␈α
should
␈β
!␈↓ β$␈ε%1
␈β
&␈↓ ↓H␈ε"occur␈α
about␈↓ βT␈ε"of␈α∞the␈α∞time,␈α∞etc.␈α∃Y␈α⎇et␈α∞if␈α
w␈α␈e␈α∞tak␈α␈e␈α∞a␈α∞truly␈α
random␈α∞sequence␈α∞of␈α
a
␈β
7␈↓ β∃␈ε%100
␈β
:␈↓ β∃␈∧
:β∃α.
␈β
Q␈↓ ↓H␈ε"million␈α
digits,␈αit␈α
will␈α
not␈α
alw␈α␈a␈α␈ys␈αha␈α␈v␈α␈e␈α
exactly␈α
100,000␈α
zeros,␈α100,000␈α
ones,␈αetc.␈α∂In
␈β
|␈↓ ↓H␈ε"fact,␈α
chances␈α
of␈α∞this␈α
are␈α
quite␈α
slim;␈α∞a␈ε/␈α
sequence␈ε"␈α
of␈α∞such␈α
sequences␈α
will␈α
ha␈α␈v␈α␈e␈α
this
␈β'␈↓ ↓H␈ε"character␈αon␈αthe␈αa␈α␈v␈α␈erage.
␈βT␈↓ α␈ε"An␈α␈y␈α∪speci|ed␈α∪sequence␈α∩of␈α∪a␈α∪million␈α∪digits␈α∪is␈α∩equally␈α∪as␈α∪probable␈α∪as␈α∩the
␈β␈␈↓ ↓H␈ε"sequence␈α	consisting␈α
of␈α	a␈α
million␈ε/␈α	zeros.␈ε"␈α⊂Th␈α␈us,␈α
if␈α	w␈α␈e␈α
are␈α	cho␈α↓osing␈α
a␈α	million␈α
digits␈α	at
␈β*␈↓ ↓H␈ε"random␈αλand␈α	if␈αλthe␈α	|rst␈αλ999,999␈α	of␈αλthem␈α	happen␈αλto␈α	come␈αλout␈α	to␈αλbe␈α	zero,␈α	the␈αλchance
␈βQ␈↓ εX␈ε%1
␈βU␈↓ ↓H␈ε"that␈αthe␈α|nal␈αdigit␈αis␈αzero␈αis␈αstill␈αexactly␈↓ εs␈ε",␈αin␈αa␈αtruly␈αrandom␈αsituation.␈α∂These
␈βf␈↓ εP␈ε%1␈α↓0
␈βj␈↓ εP␈∧jεPα∨
␈β
↓␈↓ ↓H␈ε"statemen␈α␈ts␈α	seem␈α
parado␈α␈xical␈α
to␈α
man␈α␈y␈α
people,␈α
but␈α
there␈α
is␈α
really␈α
no␈α	con␈α␈tradiction
␈β
,␈↓ ↓H␈ε"in␈α␈v␈α␈olv␈α␈ed.
␈β
X␈↓ α␈ε"There␈α
are␈α
sev␈α␈eral␈αw␈α␈a␈α␈ys␈α
to␈α
form␈α␈ulate␈αdecen␈α␈t␈α
abstract␈α
de|nitions␈α
of␈αrandom-
␈β∞β␈↓ ↓H␈ε"ness,␈α∂and␈α∂w␈α␈e␈α∂will␈α∂return␈α∂to␈α∂this␈α∂in␈α␈teresting␈α∂subject␈α∞in␈α∂Section␈α∂3.5;␈α⊃but␈α∂for␈α∞the
␈β∞/␈↓ ↓H␈ε"momen␈α␈t,␈α
let␈α
us␈αcon␈α␈ten␈α␈t␈α
ourselv␈α␈es␈α
with␈α
an␈αin␈α␈tuitiv␈α␈e␈α
understanding␈α
of␈α
the␈α
concept.
␈β∞j␈↓ α␈ε"A␈α␈t␈α
|rst,␈α
people␈αwho␈α
needed␈α
random␈α
n␈α␈um␈α␈bers␈αin␈α
their␈α
scien␈α␈ti|c␈α
w␈α␈ork␈αw␈α␈ould
␈β∂∃␈↓ ↓H␈ε"dra␈α␈w␈α∂balls␈α∂out␈α∞of␈α∂a␈α∂\w␈α␈ell-stirred␈α∂urn"␈α∂or␈α∂w␈α␈ould␈α∂roll␈α∂dice␈α∂or␈α∂deal␈α∂out␈α∂cards.␈α_A
␈β∂@␈↓ ↓H␈ε"table␈αof␈αo␈α␈v␈α␈er␈α40,000␈αrandom␈αdigits,␈α\tak␈α␈en␈αat␈αrandom␈αfrom␈αcensus␈αreports,"␈αw␈α␈as
␈β∂k␈↓ ↓H␈ε"published␈α∞in␈α∂1927␈α∂by␈α∞L.␈α∂H.␈α∂C.␈↓ ¬<␈ε"Tippett.␈α_Since␈α∞then,␈α⊂a␈α∞n␈α␈um␈α␈ber␈α∂of␈α∂devices␈α∞ha␈α␈v␈α␈e
␈β⊂⊗␈↓ ↓H␈ε"been␈α	built␈α
to␈α
generate␈α
random␈α
n␈α␈um␈α␈bers␈α
mechanically;␈↓ λ∀␈ε"the␈α
|rst␈α
such␈α
machine␈α	w␈α␈as
␈β⊂B␈↓ ↓H␈ε"used␈α∞in␈α∞1939␈α∞by␈α∞M.␈α∞G.␈↓ ∧?␈ε"Kendall␈α∂and␈α∞B.␈↓ ε@␈ε"Babington-Smith␈α∞to␈α∞produce␈α∞a␈α∞table␈α∞of
␈β⊂m␈↓ ↓H␈ε"100,000␈α
random␈αdigits,␈α
and␈α
in␈α
1955␈α
the␈↓ εB␈ε"RAND␈α
Corporation␈α
published␈α
a␈αwidely
␈β⊃_␈↓ ↓H␈ε"used␈αtable␈α
of␈α
a␈α
million␈α
random␈α
digits␈αobtained␈α
with␈α
the␈α
help␈α
of␈α
another␈αspecial
␈β∪(

␈β↓U␈↓ ↓H␈ε"3.1␈↓ ~␈ε"3
␈β↓\␈↓ λ<␈ε∞INT␈α↓R␈α␈ODU␈α↓CTION
␈βα$␈↓ ↓H␈ε"device.␈α∂A␈αfamous␈αrandom-n␈α␈um␈α␈ber␈αmachine␈αcalled␈↓ π[␈ε"ERNIE␈αhas␈αbeen␈αused␈αto␈αpick
␈βαO␈↓ ↓H␈ε"the␈α∞winning␈α∂n␈α␈um␈α␈bers␈α∞in␈α∂the␈α∂British␈α∞Premium␈α∂Sa␈α␈vings␈α∞Bonds␈α∂lottery.␈α≡[See␈α∞the
␈βαz␈↓ ↓H␈ε"articles␈α∞by␈α∂Kendall␈α∞and␈α∂Babington-Smith␈α∞in␈ε/␈α∂J.␈α∞Ro␈α␈y␈α␈al␈α∂Stat.␈α∞Soc.␈ε",␈α∂Series␈α∂A,␈ε2␈α∞101
␈ββ&␈↓ ↓H␈ε"(1938),␈α147↑166,␈αand␈αSeries␈αB,␈ε2␈α6␈ε"␈α(1939),␈α51↑61;␈αsee␈αalso␈αthe␈αreview␈αof␈αthe␈αRAND
␈ββQ␈↓ ↓H␈ε"table␈αin␈ε/␈α
Math.␈αComp.␈ε2␈α
10␈ε"␈α(1956),␈α
39↑43,␈α
and␈αthe␈α
discussion␈αof␈α
ERNIE␈αby␈α
W.␈αE.
␈ββ|␈↓ ↓H␈ε"Thomson␈αet␈αal.,␈ε/␈αJ.␈αRo␈α␈y␈α␈al␈αStat.␈αSoc.␈ε",␈αSeries␈αA,␈ε2␈α122␈ε"␈α(1959),␈α301↑333.]
␈β∧(␈↓ α␈ε"Shortly␈α
a$er␈α
computers␈α	w␈α␈ere␈α
in␈α␈troduced,␈α
people␈α
began␈α
to␈α
search␈α
for␈α	e}cien␈α␈t
␈β∧S␈↓ ↓H␈ε"w␈α␈a␈α␈ys␈α	to␈α	obtain␈α	random␈α	n␈α␈um␈α␈bers␈α	within␈α
computer␈α	programs.␈α∂A␈α	table␈α	can␈α	be␈α	used,
␈β∧}␈↓ ↓H␈ε"but␈α
this␈α
method␈α
is␈α
of␈α
limited␈α
utilit␈α␈y␈α
because␈α
of␈α
the␈α	memory␈α
space␈α
and␈α
input␈α
time
␈β¬)␈↓ ↓H␈ε"requiremen␈α␈t,␈α⊂because␈α∂the␈α∂table␈α∂ma␈α␈y␈α∂be␈α∂to␈α↓o␈α∂short,␈α⊂and␈α⊂because␈α∂it␈α∂is␈α∂a␈α∂bit␈α∂of␈α∂a
␈β¬U␈↓ ↓H␈ε"n␈α␈uisance␈α∂to␈α∂prepare␈α⊂and␈α∂main␈α␈tain␈α∂the␈α⊂table.␈α~Machines␈α∂such␈α⊂as␈α∂ERNIE␈α∂migh␈α␈t
␈βε␈↓ ↓H␈ε"be␈αattached␈αto␈αthe␈αcomputer,␈αbut␈αthis␈αw␈α␈ould␈αbe␈αunsatisfactory␈αsince␈αit␈αw␈α␈ould␈αbe
␈βε+␈↓ ↓H␈ε"impractical␈α
to␈α
reproduce␈α
calculations␈α
exactly␈α∞a␈α
second␈α
time␈α
when␈α
checking␈α
out
␈βεV␈↓ ↓H␈ε"a␈αprogram;␈αand␈αsuch␈αmachines␈αha␈α␈v␈α␈e␈αtended␈αto␈αsu{er␈αfrom␈αmalfunctions␈αthat␈αare
␈βπ↓␈↓ ↓H␈ε"di}cult␈αto␈αdetect.
␈βπ-␈↓ α␈ε"The␈α⊂inadequacy␈α⊂of␈α⊂these␈α⊂methods␈α⊂led␈α⊂to␈α⊂an␈α⊂in␈α␈terest␈α⊂in␈α⊂the␈α⊂production␈α⊂of
␈βπY␈↓ ↓H␈ε"random␈α∪n␈α␈um␈α␈bers␈α∩using␈α∪the␈α∪arithmetic␈α∪operations␈α∪of␈α∪a␈α∪computer.␈α%John␈↓ 
t␈ε"v␈α␈on
␈βλ∧␈↓ ↓H␈ε"Neumann␈α	|rst␈α
suggested␈α
this␈α
approach␈α
in␈α
about␈α	1946,␈αusing␈α
the␈↓ 	.␈ε"\middle-square"
␈βλ/␈↓ ↓H␈ε"method.␈α↔His␈α∂idea␈α∞w␈α␈as␈α∂to␈α∞tak␈α␈e␈α∂the␈α∞square␈α∂of␈α∞the␈α∂previous␈α∞random␈α∂n␈α␈um␈α␈ber␈α∞and
␈βλZ␈↓ ↓H␈ε"to␈αextract␈αthe␈αmiddle␈αdigits;␈αfor␈α
example,␈αif␈αw␈α␈e␈αare␈αgenerating␈α10-digit␈αn␈α␈um␈α␈bers
␈β	¬␈↓ ↓H␈ε"and␈αthe␈αprevious␈αv␈α}alue␈αw␈α␈as␈α5772156649,␈αw␈α␈e␈αsquare␈αit␈αto␈αget
␈β	↑␈↓ ¬↓␈ε"33317792380594909201,
␈β
6␈↓ ↓H␈ε"and␈αthe␈αnext␈αn␈α␈um␈α␈ber␈αis␈αtherefore␈α7923805949.
␈β
b␈↓ α␈ε"There␈α∂is␈α∂a␈α∂fairly␈α∂obvious␈α∂objection␈α∂to␈α∂this␈α∂technique:␈α∩ho␈α␈w␈α∂can␈α∂a␈α∂sequence
␈β
␈↓ ↓H␈ε"generated␈α
in␈α
such␈α
a␈α
w␈α␈a␈α␈y␈αbe␈α
random,␈α
since␈αeach␈α
n␈α␈um␈α␈ber␈α
is␈α
completely␈α
determined
␈β8␈↓ ↓H␈ε"by␈α
its␈α	predecessor?␈α⊂The␈α
answ␈α␈er␈α
is␈α
that␈α	this␈α
sequence␈ε/␈α
isn't␈ε"␈α
random,␈αbut␈α
it␈ε/␈α	appears
␈βd␈↓ ↓H␈ε"to␈α∞be.␈α⊗In␈α∞t␈α␈ypical␈α∞applications␈α∞the␈α∞actual␈α∞relationship␈α∞bet␈α␈w␈α␈een␈α∞one␈α∞n␈α␈um␈α␈ber␈α∞and
␈β∂␈↓ ↓H␈ε"its␈α∩successor␈α∩has␈α∩no␈α∩ph␈α␈ysical␈α∩signi|cance;␈α∃hence␈α⊃the␈α∩nonrandom␈α∩character␈α∩is
␈β:␈↓ ↓H␈ε"not␈α
really␈α
undesirable.␈α∪In␈α␈tuitiv␈α␈ely,␈α∞the␈α
middle␈α
square␈α
seems␈α
to␈α
be␈α
a␈α
fairly␈α
go␈α↓od
␈βe␈↓ ↓H␈ε"scram␈α␈bling␈αof␈αthe␈αprevious␈αn␈α␈um␈α␈ber.
␈β
⊃␈↓ α␈ε"Sequences␈α∞generated␈α∞in␈α∞a␈α∞deterministic␈α∞w␈α␈a␈α␈y␈α∞such␈α∞as␈α∞this␈α∞are␈α∞usually␈α∞called
␈β
<␈↓ ↓H␈ε/pseudo-random␈ε"␈αor␈↓ βp␈ε/quasi-random␈ε"␈α
sequences␈αin␈αthe␈α
high␈α␈bro␈α␈w␈αtechnical␈αliterature,
␈β
g␈↓ ↓H␈ε"but␈α∞in␈α∞this␈α
bo␈α↓ok␈α∞w␈α␈e␈α∞shall␈α∞simply␈α∞call␈α∞them␈α∞random␈α∞sequences,␈α∂with␈α
the␈α∞under-
␈β∞∪␈↓ ↓H␈ε"standing␈α	that␈α	they␈α	only␈ε/␈α	appear␈ε"␈α	to␈α	be␈α	random.␈α∂Being␈α	\apparen␈α␈tly␈α	random"␈α	is␈α	per-
␈β∞>␈↓ ↓H␈ε"haps␈α
all␈α
that␈αcan␈α
be␈αsaid␈α
about␈α
an␈α␈y␈αrandom␈α
sequence␈αan␈α␈yw␈α␈a␈α␈y.␈α∂Random␈α
n␈α␈um␈α␈bers
␈β∞i␈↓ ↓H␈ε"generated␈α
deterministically␈αon␈αcomputers␈αha␈α␈v␈α␈e␈αw␈α␈ork␈α␈ed␈α
quite␈αw␈α␈ell␈αin␈αnearly␈α
ev␈α␈ery
␈β∂∀␈↓ ↓H␈ε"application,␈α⊃pro␈α␈vided␈α⊃that␈α⊂a␈α⊂suitable␈α⊃method␈α⊂has␈α⊂been␈α⊃carefully␈α⊂selected.␈α≥Of
␈β∂?␈↓ ↓H␈ε"course,␈α	deterministic␈αλsequences␈αλaren't␈α	alw␈α␈a␈α␈ys␈αλthe␈αλansw␈α␈er;␈α
they␈αλcertainly␈αλshouldn't
␈β∂k␈↓ ↓H␈ε"replace␈αERNIE␈αfor␈αthe␈αlotteries.
␈β⊂⊗␈↓ α␈ε"V␈α⎇on␈α	Neumann's␈α	original␈α	\middle-square␈α	method"␈α	has␈α	actually␈α	pro␈α␈v␈α␈ed␈α	to␈α	be␈αλa
␈β⊂B␈↓ ↓H␈ε"comparativ␈α␈ely␈αpo␈α↓or␈αsource␈αof␈αrandom␈αn␈α␈um␈α␈bers.␈α⊂The␈αdanger␈αis␈αthat␈αthe␈αsequence
␈β⊂m␈↓ ↓H␈ε"tends␈αto␈αget␈αin␈α␈to␈αa␈αrut,␈αa␈αshort␈αcy␈α␈cle␈αof␈αrepeating␈αelemen␈α␈ts.␈α⊂F␈α⎇or␈αexample,␈αif␈αzero
␈β⊃_␈↓ ↓H␈ε"ev␈α␈er␈αappears␈αas␈αa␈αn␈α␈um␈α␈ber␈αof␈αthe␈αsequence,␈αit␈αwill␈αcon␈α␈tin␈α␈ually␈αperpetuate␈αitself.
␈β∪(

␈β↓U␈↓ ↓H␈ε"4␈↓ 
}␈ε"3.1
␈β↓\␈↓ α=␈ε∞RANDOM␈α
NU␈α↓MB␈α␈E␈α↓RS
␈βα$␈↓ α␈ε"Sev␈α␈eral␈α⊃people␈α⊂experimen␈α␈ted␈α⊃with␈α⊂the␈α⊂middle-square␈α⊃method␈α⊂in␈α⊃the␈α⊂early
␈βαO␈↓ ↓H␈ε"1950s.␈α∂W␈α⎇orking␈α	with␈α	n␈α␈um␈α␈bers␈α	that␈α	ha␈α␈v␈α␈e␈α	four␈α	digits␈α	instead␈α	of␈α
ten,␈α	G.␈α	E.␈↓ 
$␈ε"F␈α⎇orsythe
␈βαz␈↓ ↓H␈ε"tried␈α⊂16␈α⊂di{eren␈α␈t␈α⊂starting␈α⊂v␈α}alues␈α⊂and␈α⊂found␈α⊂that␈α⊂12␈α⊂of␈α⊂them␈α⊂led␈α⊂to␈α⊂sequences
␈ββ&␈↓ ↓H␈ε"ending␈α⊃with␈α∩the␈α⊃cy␈α␈cle␈α∩6100,␈α∪2100,␈α∪4100,␈α∪8100,␈α∪6100,␈↓ λ3␈ε".␈αε.␈αε.␈↓ λc␈ε",␈α∪while␈α⊃t␈α␈w␈α␈o␈α∩of␈α⊃them
␈ββQ␈↓ ↓H␈ε"degenerated␈α	to␈α
zero.␈α∂N.␈↓ ∧@␈ε"Metropolis␈α
also␈α
conducted␈α	extensiv␈α␈e␈α
tests␈α
on␈α
the␈α	middle-
␈ββ|␈↓ ↓H␈ε"square␈αmethod,␈α
mostly␈αin␈αthe␈α
binary␈αn␈α␈um␈α␈ber␈α
system.␈α⊃He␈αsho␈α␈w␈α␈ed␈α
that␈αwhen␈α20-
␈β∧'␈↓ ↓H␈ε"bit␈αn␈α␈um␈α␈bers␈αare␈αbeing␈αused,␈αthere␈αare␈α13␈αdi{eren␈α␈t␈αcy␈α␈cles␈αin␈α␈to␈αwhich␈α
the␈αsequence
␈β∧R␈↓ ↓H␈ε"migh␈α␈t␈αdegenerate,␈αthe␈αlongest␈αof␈αwhich␈αhas␈αa␈αperiod␈αof␈αlength␈α142.
␈β∧}␈↓ α␈ε"It␈α∞is␈α∞fairly␈α∞easy␈α∞to␈α∞restart␈α∞the␈α∞middle-square␈α∞method␈α∞on␈α∞a␈α∞new␈α
v␈α}alue␈α∞when
␈β¬)␈↓ ↓H␈ε"zero␈α	has␈α
been␈α
detected,␈α
but␈α
long␈α
cy␈α␈cles␈α
are␈α
somewhat␈α
harder␈α	to␈α
a␈α␈v␈α␈oid.␈α⊂Exercise␈α	7
␈β¬T␈↓ ↓H␈ε"discusses␈α∂some␈α⊂in␈α␈teresting␈α∂w␈α␈a␈α␈ys␈α⊂to␈α∂determine␈α⊂the␈↓ πj␈ε"cy␈α␈cles␈α∂of␈α⊂periodic␈α∂sequences,
␈β¬␈␈↓ ↓H␈ε"using␈αv␈α␈ery␈αlittle␈αmemory␈αspace.
␈βε*␈↓ α␈ε"A␈α
theoretical␈αdisadv␈α}an␈α␈tage␈α
of␈α
the␈α
middle-square␈α
method␈αis␈α
giv␈α␈en␈α
in␈α
exercises
␈βεV␈↓ ↓H␈ε"9␈αλand␈αλ10.␈α∂On␈αλthe␈αλother␈αλhand,␈α	w␈α␈orking␈αλwith␈αλ38-bit␈αλn␈α␈um␈α␈bers,␈α	Metropolis␈αλobtained␈αλa
␈βπ↓␈↓ ↓H␈ε"sequence␈α	of␈αλabout␈α	750,000␈α	n␈α␈um␈α␈bers␈α	before␈α	degeneracy␈α	occurred,␈α
and␈α	the␈αλresulting
␈βπ,␈↓ ↓H␈ε"750,000␈ε6␈αα␈ε"␈α38␈α⊃bits␈α⊂satisfactorily␈α⊃passed␈α⊃statistical␈α⊃tests␈α⊂for␈α⊃randomness.␈α≡This
␈βπW␈↓ ↓H␈ε"sho␈α␈ws␈α∂that␈α∂the␈α⊂middle-square␈α∂method␈ε/␈α⊂can␈ε"␈α∂giv␈α␈e␈α⊂usable␈α∂results,␈α⊂but␈α⊂it␈α∂is␈α∂rather
␈βλα␈↓ ↓H␈ε"dangerous␈αto␈α
put␈αm␈α␈uch␈α
faith␈αin␈α
it␈αun␈α␈til␈α
a$er␈αelaborate␈αcomputations␈α
ha␈α␈v␈α␈e␈αbeen
␈βλ.␈↓ ↓H␈ε"performed.
␈βλa␈↓ α␈ε"Man␈α␈y␈α
random␈α
n␈α␈um␈α␈ber␈α
generators␈α
in␈αuse␈α
toda␈α␈y␈α
are␈α
not␈α
v␈α␈ery␈α
go␈α↓od.␈α∪There␈αis
␈β	␈↓ ↓H␈ε"a␈α
tendency␈α
for␈αpeople␈α
to␈α
a␈α␈v␈α␈oid␈α
learning␈α
an␈α␈ything␈α
about␈α
such␈α
subroutines;␈α
quite
␈β	7␈↓ ↓H␈ε"o$en␈α⊂w␈α␈e␈α⊂|nd␈α⊂that␈α⊂some␈α⊂old␈α⊃method␈α⊂that␈α⊂is␈α⊂comparativ␈α␈ely␈α⊂unsatisfactory␈α⊂has
␈β	c␈↓ ↓H␈ε"blindly␈α∞been␈α∞passed␈α∞do␈α␈wn␈α∞from␈α∂one␈α∞programmer␈α∞to␈α∞another,␈α∂and␈α∞toda␈α␈y's␈α∞users
␈β
∞␈↓ ↓H␈ε"ha␈α␈v␈α␈e␈α
no␈αunderstanding␈α
of␈α
its␈α
limitations.␈α∪W␈α⎇e␈α
shall␈α
see␈α
in␈α
this␈α
chapter␈α
that␈α
it␈αis
␈β
9␈↓ ↓H␈ε"not␈αdi}cult␈αto␈αlearn␈αthe␈αmost␈αimportan␈α␈t␈αfacts␈αabout␈αrandom␈αn␈α␈um␈α␈ber␈αgenerators
␈β
d␈↓ ↓H␈ε"and␈αtheir␈αproper␈αuse.
␈β∂␈↓ α␈ε"It␈α
is␈αnot␈α
easy␈αto␈α
in␈α␈v␈α␈en␈α␈t␈α
a␈αfo␈α↓olpro␈α↓of␈α
source␈α
of␈αrandom␈α
n␈α␈um␈α␈bers.␈↓ 	]␈ε"This␈α
fact␈α
w␈α␈as
␈β;␈↓ ↓H␈ε"con␈α␈vincingly␈α∞impressed␈α∞upon␈α∞the␈α∞author␈α∞sev␈α␈eral␈α∞y␈α␈ears␈α∂ago,␈α∞when␈α∞he␈α∞attempted
␈βf␈↓ ↓H␈ε"to␈αcreate␈αa␈αfan␈α␈tastically␈αgo␈α↓od␈αgenerator␈αusing␈αthe␈αfollo␈α␈wing␈αpeculiar␈αapproach:
␈β!␈↓ ↓H␈ε2Algorithm␈α⊃K␈ε"␈α∩(␈ε/␈αz\Super-random"␈α∩n␈α␈um␈α␈ber␈α∩generator␈↓ π`␈ε")␈ε2.␈ε"␈α#Giv␈α␈en␈α∩a␈α∩10-digit␈α⊃decimal
␈βL␈↓ ↓H␈ε"n␈α␈um␈α␈ber␈↓ αJ␈ε(X␈↓ αl␈ε",␈αthis␈αalgorithm␈αma␈α␈y␈αbe␈αused␈αto␈αchange␈↓ π←␈ε(X␈↓ λ
␈ε"to␈αthe␈αn␈α␈um␈α␈ber␈αthat␈αshould
␈βx␈↓ ↓H␈ε"come␈αnext␈α
in␈αa␈α
supposedly␈αrandom␈α
sequence.␈α⊃Although␈α
the␈αalgorithm␈α
migh␈α␈t␈αbe
␈β
#␈↓ ↓H␈ε"expected␈α⊂to␈α⊂yield␈α⊂quite␈α⊂a␈α⊂random␈α⊂sequence,␈α⊃reasons␈α⊂giv␈α␈en␈α⊂belo␈α␈w␈α⊂sho␈α␈w␈α⊂that␈α⊂it
␈β
N␈↓ ↓H␈ε"is,␈α∞in␈α∞fact,␈α∞not␈α∞v␈α␈ery␈α
go␈α↓od␈α∞at␈α∞all.␈α≤(The␈α∞reader␈α∞need␈α
not␈α∞study␈α∞this␈α∞algorithm␈α
in
␈β
y␈↓ ↓H␈ε"great␈α∞detail␈α∂except␈α∞to␈α∞observ␈α␈e␈α∂ho␈α␈w␈α∞complicated␈α∂it␈α∞is;␈α⊂note,␈α∂in␈α∞particular,␈α∂steps
␈β∞$␈↓ ↓H␈ε"K1␈αand␈αK2.)
␈β∞R␈↓ λ(␈ε%9
␈β∞X␈↓ ↓Z␈ε2K1.␈↓ α≠␈ε"[Cho␈α↓ose␈α⊂n␈α␈um␈α␈ber␈α∂of␈α⊂iterations.]␈α∨Set␈↓ εb␈ε(Y␈↓ π∞␈ε6␈ ␈α⊂b␈↓ πP␈ε(X␈↓ πr␈ε"/1␈↓ λ⊗␈ε"0␈↓ λ9␈ε6c␈ε"␈α∂,␈α⊂the␈α⊂most␈α∂signi|can␈α␈t
␈β∂β␈↓ α≡␈ε"digit␈α
of␈↓ β≡␈ε(X␈↓ β?␈ε".␈α≠(W␈α⎇e␈α
will␈α
execute␈αsteps␈α
K2␈α
through␈αK13␈α
exactly␈↓ 	↑␈ε(Y␈↓ 
β␈ε"+␈α	1␈αtimes;
␈β∂.␈↓ α≡␈ε"that␈α∂is,␈α⊃w␈α␈e␈α∂will␈α∂apply␈α⊂randomizing␈α∂transformations␈α∂a␈ε/␈α⊂random␈ε"␈α∂n␈α␈um␈α␈ber␈α∂of
␈β∂Y␈↓ α≡␈ε"times.)
␈β⊂ε␈↓ π∂␈ε%8
␈β⊂
␈↓ ↓Z␈ε2K2.␈↓ α≠␈ε"[Cho␈α↓ose␈α
random␈αstep.]␈α≠Set␈↓ ¬T␈ε(Z␈↓ ¬z␈ε6␈ ␈αb␈↓ ε7␈ε(X␈↓ εY␈ε"/1␈↓ ε⎇␈ε"0␈↓ π ␈ε6c␈↓ π4␈ε"mod␈↓ π}␈ε"10,␈α
the␈αsecond␈α
most␈αsigni|-
␈β⊂8␈↓ α≡␈ε"can␈α␈t␈αdigit␈αof␈↓ βg␈ε(X␈↓ ∧	␈ε".␈α⊂Go␈αto␈αstep␈α
K(3␈αε+␈↓ ε;␈ε(Z␈↓ εV␈ε").␈α∃(That␈α
is,␈αw␈α␈e␈αno␈α␈w␈αjump␈αto␈αa␈ε/␈α
random
␈β⊂c␈↓ α≡␈ε"step␈αin␈αthe␈αprogram.)
␈β⊃⊂␈↓ ∧5␈ε%9
␈β⊃⊗␈↓ ↓Z␈ε2K3.␈↓ α≠␈ε"[Ensure␈ε6␈α∃␈ε"␈α
5␈ε6␈αλα␈ε"␈αλ1␈↓ ∧#␈ε"0␈↓ ∧F␈ε".]␈α→If␈↓ ¬↔␈ε(X␈↓ ¬C␈ε"<␈α
5000000000,␈αset␈↓ πs␈ε(X␈↓ λ∨␈ε6␈ ␈↓ λM␈ε(X␈↓ λw␈ε"+␈αλ5000000000.
␈β∪(

␈β↓U␈↓ ↓H␈ε"3.1␈↓ ~␈ε"5
␈β↓\␈↓ λ<␈ε∞INT␈α↓R␈α␈ODU␈α↓CTION
␈βα≤␈↓ εN␈ε%2␈↓ π∃␈ε%5␈↓ λ'␈ε%1␈α↓0
␈βα"␈↓ ↓Z␈ε2K4.␈↓ α≠␈ε"[Middle␈α
square.]␈α≠Replace␈↓ ¬;␈ε(X␈↓ ¬j␈ε"by␈ε6␈α
b␈↓ ε,␈ε(X␈↓ ε←␈ε"/1␈↓ πβ␈ε"0␈↓ π%␈ε6c␈↓ π9␈ε"mod␈↓ λβ␈ε"1␈↓ λ∃␈ε"0␈↓ λG␈ε",␈α∞i.e.,␈α
by␈α
the␈α
middle␈α
of
␈βαM␈↓ α≡␈ε"the␈αsquare␈αof␈↓ βv␈ε(X␈↓ ∧_␈ε".
␈ββλ␈↓ λ*␈ε%1␈α↓0
␈ββ∂␈↓ ↓Z␈ε2K5.␈↓ α≠␈ε"[Multiply.]␈α→Replace␈↓ ∧a␈ε(X␈↓ ¬∂␈ε"by␈α(1001001001␈↓ πλ␈ε(X␈↓ π*␈ε")␈↓ π<␈ε"mod␈↓ λε␈ε"1␈↓ λ_␈ε"0␈↓ λJ␈ε".
␈ββP␈↓ ↓Z␈ε2K6.␈↓ α≠␈ε"[Pseudo-complemen␈α␈t.]␈α∃If␈↓ ¬*␈ε(X␈↓ ¬V␈ε"<␈α
100000000,␈αthen␈αset␈↓ λC␈ε(X␈↓ λo␈ε6␈ ␈↓ 	≥␈ε(X␈↓ 	E␈ε"+␈α¬9814055677;
␈ββu␈↓ ∧t␈ε%10
␈ββ{␈↓ α≡␈ε"otherwise␈αset␈↓ βv␈ε(X␈↓ ∧"␈ε6␈ ␈ε"␈α
1␈↓ ∧b␈ε"0␈↓ ¬≤␈ε6␈␈↓ ¬H␈ε(X␈↓ ¬j␈ε".
␈β∧<␈↓ ↓Z␈ε2K7.␈↓ α≠␈ε"[In␈α␈terchange␈α∞halv␈α␈es.]␈α≥In␈α␈terchange␈α∞the␈α∂lo␈α␈w-order␈α∞|v␈α␈e␈α∞digits␈α∞of␈↓ 	v␈ε(X␈↓ 
&␈ε"with␈α∞the
␈β∧a␈↓ ε:␈ε%5␈↓ πm␈ε%5␈↓ 	!␈ε%5
␈β∧g␈↓ α≡␈ε"high-order␈α|v␈α␈e␈αdigits,␈αi.e.,␈↓ ¬<␈ε(X␈↓ ¬h␈ε6␈ ␈ε"␈α
1␈↓ ε(␈ε"0␈↓ εK␈ε"(␈↓ εW␈ε(X␈↓ ε␈␈ε"mod␈↓ πI␈ε"1␈↓ π[␈ε"0␈↓ π}␈ε")␈αε+␈ε6␈απb␈↓ λI␈ε(X␈↓ λk␈ε"/1␈↓ 	∂␈ε"0␈↓ 	2␈ε6c␈ε",␈αthe␈αmiddle␈α10
␈β¬␈↓ βZ␈ε%10
␈β¬∩␈↓ α≡␈ε"digits␈αof␈α(1␈↓ βH␈ε"0␈↓ ∧α␈ε"+␈αλ1)␈↓ ∧L␈ε(X␈↓ ∧n␈ε".
␈β¬S␈↓ ↓Z␈ε2K8.␈↓ α≠␈ε"[Multiply.]␈α→Same␈αas␈αstep␈αK5.
␈βε∀␈↓ ↓Z␈ε2K9.␈↓ α≠␈ε"[Decrease␈α
digits.]␈α⊃Decrease␈α	each␈α
nonzero␈α
digit␈α	of␈α
the␈α
decimal␈α	represen␈α␈tation
␈βε@␈↓ α≡␈ε"of␈↓ αH␈ε(X␈↓ αv␈ε"by␈αone.
␈βε{␈↓ ¬X␈ε%5␈↓ π@␈ε%2
␈βπ↓␈↓ ↓H␈ε2K10.␈↓ α≠␈ε"[99999␈α∂modify.]␈α≥If␈↓ ∧R␈ε(X␈↓ ¬α␈ε"<␈α∞1␈↓ ¬F␈ε"0␈↓ ¬i␈ε",␈α∂set␈↓ ε<␈ε(X␈↓ εl␈ε6␈ ␈↓ π≡␈ε(X␈↓ π[␈ε"+␈α	99999;␈α⊂otherwise␈α∞set␈↓ 
Y␈ε(X␈↓ λ␈ε6␈ 
␈βπ,␈↓ α≡␈ε(X␈↓ αH␈ε6␈␈ε"␈αλ99999.
␈βπg␈↓ 	/␈ε%9
␈βπm␈↓ ↓H␈ε2K11.␈↓ α≠␈ε"[Normalize.]␈α↔(A␈α␈t␈αthis␈αpoin␈α␈t␈↓ ¬O␈ε(X␈↓ ¬⎇␈ε"cannot␈αbe␈αzero.)␈α↔If␈↓ λ1␈ε(X␈↓ λ]␈ε"<␈α
1␈↓ 	≥␈ε"0␈↓ 	@␈ε",␈αset␈↓ 
␈ε(X␈↓ 
8␈ε6␈ ␈ε"␈α
10␈↓ 
␈ε(X
␈βλ_␈↓ α≡␈ε"and␈αrepeat␈αthis␈αstep.
␈βλS␈↓ λ{␈ε%5␈↓ 
∞␈ε%10
␈βλY␈↓ ↓H␈ε2K12.␈↓ α≠␈ε"[Modi|ed␈αmiddle␈α
square.]␈α∪Replace␈↓ ε>␈ε(X␈↓ εj␈ε"by␈ε6␈αb␈↓ π*␈ε(X␈↓ πL␈ε"(␈↓ πX␈ε(X␈↓ π}␈ε6␈␈ε"␈α¬1)/1␈↓ λi␈ε"0␈↓ 	␈ε6c␈↓ 	 ␈ε"mod␈↓ 	j␈ε"1␈↓ 	|␈ε"0␈↓ 
.␈ε",␈αi.e.,␈α
by
␈β	¬␈↓ α≡␈ε"the␈αmiddle␈α10␈αdigits␈αof␈↓ ¬∞␈ε(X␈↓ ¬0␈ε"(␈↓ ¬<␈ε(X␈↓ ¬f␈ε6␈␈ε"␈αλ1).
␈β	F␈↓ ↓H␈ε2K13.␈↓ α≠␈ε"[Repeat?]␈α↔If␈↓ βh␈ε(Y␈↓ ∧∞␈ε">␈α
0,␈αdecrease␈↓ ¬q␈ε(Y␈↓ ε→␈ε"by␈α1␈αand␈αreturn␈αto␈αstep␈αK2.␈α⊂If␈↓ 	}␈ε(Y␈↓ 
%␈ε"=␈α
0,␈αthe
␈β	q␈↓ α≡␈ε"algorithm␈αterminates␈αwith␈↓ ¬F␈ε(X␈↓ ¬t␈ε"as␈αthe␈αdesired␈α\random"␈αv␈α}alue.
␈β	z␈↓ 
β␈∧	z
β≠∂
␈β
E␈↓ ↓H␈ε"(The␈α∞machine-language␈α∞program␈α∞corresponding␈α∞to␈α∞the␈α∞abo␈α␈v␈α␈e␈α∞algorithm␈α∞w␈α␈as␈α∞in-
␈β
p␈↓ ↓H␈ε"tended␈α∂to␈α⊂be␈α⊂so␈α∂complicated␈α⊂that␈α∂a␈α⊂person␈α⊂reading␈α∂a␈α⊂listing␈α⊂of␈α∂it␈α⊂without␈α∂ex-
␈β≠␈↓ ↓H␈ε"planatory␈αcommen␈α␈ts␈αw␈α␈ouldn't␈αkno␈α␈w␈αwhat␈αthe␈αprogram␈αw␈α␈as␈αdoing.)
␈βI␈↓ α␈ε"Considering␈α⊂all␈α∂the␈α⊂con␈α␈tortions␈α⊂of␈α∂Algorithm␈α⊂K␈↓ λ¬␈ε",␈α⊂doesn't␈α⊂it␈α⊂seem␈α∂plausible
␈βu␈↓ ↓H␈ε"that␈α∞it␈α∞should␈α∞produce␈α∞almost␈α∞an␈α∂in|nite␈α∞supply␈α∞of␈α∞un␈α␈believ␈α}ably␈α∞random␈α∞n␈α␈um-
␈β ␈↓ ↓H␈ε"bers?␈α⊂No!␈α⊃In␈αfact,␈αwhen␈αthis␈αalgorithm␈αw␈α␈as␈α|rst␈α
put␈αon␈α␈to␈αa␈αcomputer,␈αit␈αalmost
␈βK␈↓ ↓H␈ε"immediately␈α
con␈α␈v␈α␈erged␈α∞to␈α
the␈α∞10-digit␈α
v␈α}alue␈α∞6065038420,␈α∞which←by␈α
extraordi-
␈βv␈↓ ↓H␈ε"nary␈α	coincidence←is␈α
transformed␈α	in␈α␈to␈α
itself␈α	by␈α
the␈α
algorithm␈α	(see␈α
T␈α⎇able␈α	1).␈α∂With
␈β
!␈↓ ↓H␈ε"another␈α∞starting␈α∂n␈α␈um␈α␈ber,␈α∂the␈α∞sequence␈α∂began␈α∂to␈α∞repeat␈α∂a$er␈α∞7401␈α∂v␈α}alues,␈α∂in␈α∞a
␈β
M␈↓ ↓H␈ε"cy␈α␈clic␈αperiod␈αof␈αlength␈α3178.
␈β
{␈↓ α␈ε"The␈α∂moral␈α∂of␈α∂this␈α⊂story␈α∂is␈α∂that␈ε/␈α∂random␈α∂n␈α␈um␈α␈bers␈α∂should␈α∂not␈α∂be␈α∂generated
␈β∞&␈↓ ↓H␈ε/with␈αa␈αmethod␈αchosen␈αat␈αrandom.␈ε"␈α⊂Some␈αtheory␈αshould␈αbe␈αused.
␈β∞g␈↓ α␈ε"In␈α∂this␈α∂chapter,␈α⊂w␈α␈e␈α∂shall␈α∂consider␈α∂random␈α∂n␈α␈um␈α␈ber␈α∂generators␈α∂that␈α∞are␈α∂su-
␈β∂∩␈↓ ↓H␈ε"perior␈α
to␈α
the␈α
middle-square␈α
method␈α
and␈α
to␈α
Algorithm␈α∞K␈↓ λE␈ε";␈α
the␈α
corresponding␈α
se-
␈β∂=␈↓ ↓H␈ε"quences␈α∩are␈α∩guaran␈α␈teed␈α⊃to␈α∩ha␈α␈v␈α␈e␈α∩certain␈α∩desirable␈α∩random␈α∩properties,␈α∀and␈α⊃no
␈β∂h␈↓ ↓H␈ε"degeneracy␈α∂will␈α∂occur.␈α→W␈α⎇e␈α∂shall␈α∂explore␈α∂the␈α∂reasons␈α∞for␈α∂this␈α∂random␈α∂beha␈α␈vior
␈β⊂∀␈↓ ↓H␈ε"in␈α
some␈α∞detail,␈α∞and␈α∞w␈α␈e␈α∞shall␈α∞also␈α
consider␈α∞techniques␈α∞for␈α∞manipulating␈α
random
␈β⊂?␈↓ ↓H␈ε"n␈α␈um␈α␈bers.␈α⊂F␈α⎇or␈αexample,␈α
one␈αof␈αour␈αin␈α␈v␈α␈estigations␈αwill␈α
be␈αthe␈αsh␈α␈u␈␈ing␈αof␈αa␈αsim␈α␈u-
␈β⊂j␈↓ ↓H␈ε"lated␈αdeck␈αof␈αcards␈αwithin␈αa␈αcomputer␈αprogram.
␈β⊃_␈↓ α␈ε"Section␈α3.6␈αsummarizes␈αthis␈αchapter␈αand␈αlists␈αsev␈α␈eral␈αbibliographic␈αsources.
␈β∪(

␈β↓U␈↓ ↓H␈ε"6␈↓ 
}␈ε"3.1
␈β↓\␈↓ α=␈ε∞RANDOM␈α
NU␈α↓MB␈α␈E␈α↓RS
␈βα→␈↓ ¬|␈ε=T␈α⎇able␈α
1
␈βαF␈↓ β⊂␈ε$A␈α⊂COL␈α␈OSSAL␈α⊃CO␈α␈I␈α↓N␈α␈C␈α↓IDENCE␈α↓:␈α∂THE␈α⊃N␈α␈U␈α↓MBE␈α↓R␈α∂6␈α↓0650␈α↓384␈α↓20
␈βαf␈↓ β≥␈ε$IS␈α⊂TRAN␈α␈SFORMED␈α⊂INTO␈α∂I␈α↓TSEL␈α↓F␈α⊂BY␈α⊂AL␈α␈GORITHM␈α⊂K.
␈ββ
␈↓ ↓H␈∧β
↓Hα	e
␈ββ∂␈↓ ε9␈∧β∂ε9π↑α
␈ββ!␈↓ α+␈ε#Ste␈α␈p␈↓ β?␈ε)X␈↓ βj␈ε#(a␈α␈$er)␈↓ ε⎇␈ε#Step␈↓ λ∩␈ε)X␈↓ λ<␈ε#(a␈α␈$␈α↓e␈α␈r)
␈ββS␈↓ ε⎇␈ε#K9␈↓ λ↓␈ε#1␈α␈107␈α␈855␈α␈700
␈ββg␈↓ α+␈ε#K1␈↓ β/␈ε#6␈α␈065␈α␈03␈α␈842␈α␈0
␈ββ{␈↓ ε⎇␈ε#K10␈↓ λ↓␈ε#1␈α␈107␈α␈755␈α␈701
␈β∧∂␈↓ α+␈ε#K3␈↓ β/␈ε#6␈α␈065␈α␈03␈α␈842␈α␈0
␈β∧"␈↓ ε⎇␈ε#K11␈↓ λ↓␈ε#1␈α␈107␈α␈755␈α␈701
␈β∧6␈↓ α+␈ε#K4␈↓ β/␈ε#6␈α␈910␈α␈36␈α␈076␈α␈0
␈β∧J␈↓ ε⎇␈ε#K12␈↓ λ↓␈ε#1␈α␈226␈α␈919␈α␈902␈↓ 	j␈ε)Y␈↓ 
∞␈ε#=␈α	3
␈β∧↑␈↓ α+␈ε#K5␈↓ β/␈ε#8␈α␈031␈α␈12␈α␈076␈α␈0
␈β∧r␈↓ ε⎇␈ε#K5␈↓ λ↓␈ε#0␈α␈048␈α␈821␈α␈902
␈⬬␈↓ α+␈ε#K6␈↓ β/␈ε#1␈α␈968␈α␈87␈α␈924␈α␈0
␈β¬→␈↓ ε⎇␈ε#K6␈↓ λ↓␈ε#9␈α␈862␈α␈877␈α␈579
␈β¬-␈↓ α+␈ε#K7␈↓ β/␈ε#7␈α␈924␈α␈01␈α␈968␈α␈8
␈β¬A␈↓ ε⎇␈ε#K7␈↓ λ↓␈ε#7␈α␈757␈α␈998␈α␈628
␈β¬U␈↓ α+␈ε#K8␈↓ β/␈ε#9␈α␈631␈α␈70␈α␈768␈α␈8
␈β¬h␈↓ ε⎇␈ε#K8␈↓ λ↓␈ε#2␈α␈384␈α␈626␈α␈628
␈β¬|␈↓ α+␈ε#K9␈↓ β/␈ε#8␈α␈520␈α␈60␈α␈657␈α␈7
␈βε⊂␈↓ ε⎇␈ε#K9␈↓ λ↓␈ε#1␈α␈273␈α␈515␈α␈517
␈βε$␈↓ α+␈ε#K10␈↓ β/␈ε#8␈α␈520␈α␈50␈α␈657␈α␈8
␈βε8␈↓ ε⎇␈ε#K10␈↓ λ↓␈ε#1␈α␈273␈α␈415␈α␈518
␈βεK␈↓ α+␈ε#K11␈↓ β/␈ε#8␈α␈520␈α␈50␈α␈657␈α␈8
␈βε←␈↓ ε⎇␈ε#K11␈↓ λ↓␈ε#1␈α␈273␈α␈415␈α␈518
␈βεs␈↓ α+␈ε#K12␈↓ β/␈ε#0␈α␈323␈α␈37␈α␈220␈α␈7␈↓ ¬_␈ε)Y␈↓ ¬<␈ε#=␈α	6
␈βππ␈↓ ε⎇␈ε#K12␈↓ λ↓␈ε#5␈α␈870␈α␈802␈α␈097␈↓ 	j␈ε)Y␈↓ 
∞␈ε#=␈α	2
␈βπ≠␈↓ α+␈ε#K6␈↓ β/␈ε#9␈α␈676␈α␈62␈α␈779␈α␈3
␈βπ.␈↓ ε⎇␈ε#K11␈↓ λ↓␈ε#5␈α␈870␈α␈802␈α␈097
␈βπB␈↓ α+␈ε#K7␈↓ β/␈ε#2␈α␈779␈α␈39␈α␈676␈α␈6
␈βπV␈↓ ε⎇␈ε#K12␈↓ λ↓␈ε#3␈α␈172␈α␈562␈α␈687␈↓ 	j␈ε)Y␈↓ 
∞␈ε#=␈α	1
␈βπj␈↓ α+␈ε#K8␈↓ β/␈ε#4␈α␈942␈α␈16␈α␈276␈α␈6
␈βπ}␈↓ ε⎇␈ε#K4␈↓ λ↓␈ε#1␈α␈540␈α␈029␈α␈446
␈βλ⊃␈↓ α+␈ε#K9␈↓ β/␈ε#3␈α␈831␈α␈05␈α␈165␈α␈5
␈βλ%␈↓ ε⎇␈ε#K5␈↓ λ↓␈ε#7␈α␈015␈α␈475␈α␈446
␈βλ9␈↓ α+␈ε#K10␈↓ β/␈ε#3␈α␈830␈α␈95␈α␈165␈α␈6
␈βλM␈↓ ε⎇␈ε#K6␈↓ λ↓␈ε#2␈α␈984␈α␈524␈α␈554
␈βλa␈↓ α+␈ε#K11␈↓ β/␈ε#3␈α␈830␈α␈95␈α␈165␈α␈6
␈βλt␈↓ ε⎇␈ε#K7␈↓ λ↓␈ε#2␈α␈455␈α␈429␈α␈845
␈β	λ␈↓ α+␈ε#K12␈↓ β/␈ε#1␈α␈905␈α␈86␈α␈778␈α␈1␈↓ ¬_␈ε)Y␈↓ ¬<␈ε#=␈α	5
␈β	≤␈↓ ε⎇␈ε#K8␈↓ λ↓␈ε#2␈α␈730␈α␈274␈α␈845
␈β	0␈↓ α+␈ε#K12␈↓ β/␈ε#3␈α␈319␈α␈96␈α␈747␈α␈9␈↓ ¬_␈ε)Y␈↓ ¬<␈ε#=␈α	4
␈β	D␈↓ ε⎇␈ε#K9␈↓ λ↓␈ε#1␈α␈620␈α␈163␈α␈734
␈β	W␈↓ α+␈ε#K6␈↓ β/␈ε#6␈α␈680␈α␈03␈α␈252␈α␈1
␈β	k␈↓ ε⎇␈ε#K10␈↓ λ↓␈ε#1␈α␈620␈α␈063␈α␈735
␈β	␈␈↓ α+␈ε#K7␈↓ β/␈ε#3␈α␈252␈α␈16␈α␈680␈α␈0
␈β
∪␈↓ ε⎇␈ε#K11␈↓ λ↓␈ε#1␈α␈620␈α␈063␈α␈735
␈β
'␈↓ α+␈ε#K8␈↓ β/␈ε#2␈α␈218␈α␈96␈α␈680␈α␈0
␈β
:␈↓ ε⎇␈ε#K12␈↓ λ↓␈ε#6␈α␈065␈α␈038␈α␈420␈↓ 	j␈ε)Y␈↓ 
∞␈ε#=␈α	0
␈β
l␈↓ ↓H␈∧
l↓Hα	e
␈β@␈↓ ↓H␈ε=E␈α␈XERCISES
␈β⊂␈↓ ↓;␈ε↓x
␈β∩␈↓ ↓g␈ε31.␈↓ α␈ε#[␈ε)20␈↓ α;␈ε#]␈α⊗S␈α␈up␈α␈po␈α␈se␈α⊂th␈α␈at␈α∂y␈α␈ou␈α∂wish␈α∂to␈α∂ob␈α␈tain␈α∂a␈α⊂d␈α␈ecima␈α␈l␈α⊂digit␈α∂at␈α⊂ra␈α␈nd␈α␈om,␈α⊃n␈α␈ot␈α∂using␈α∂a
␈β:␈↓ ↓H␈ε#c␈α␈omp␈α␈uter.␈α∂Wh␈α␈i␈α↓c␈α␈h␈αof␈αth␈α␈e␈αfoll␈α↓o␈α}wi␈α↓n␈α␈g␈αme␈α␈tho␈α␈ds␈αw␈α␈ou␈α␈l␈α↓d␈α
be␈αs␈α␈uitab␈α␈l␈α↓e␈α␈?
␈βm␈↓ ↓e␈ε#a)␈↓ α␈ε#Op␈α␈en␈αa␈α
telep␈α␈ho␈α␈ne␈αdirecto␈α␈ry␈α
to␈αa␈αran␈α␈dom␈αpla␈α␈ce␈α
(i.e.,␈α∞stick␈αy␈α␈o␈α␈ur␈α
|␈α␈ng␈α␈er␈α
in␈αit␈α
some␈α␈-
␈β
∃␈↓ α␈ε#whe␈α␈re)␈αan␈α␈d␈αuse␈α
the␈αu␈α␈nits␈αdig␈α␈i␈α↓t␈αo␈α␈f␈αth␈α␈e␈α|␈α␈rst␈αn␈α␈u␈α␈m␈α␈ber␈αfo␈α␈un␈α␈d␈αon␈α
the␈αse␈α␈l␈α↓e␈α␈cted␈αp␈α␈ag␈α␈e.
␈β
=␈↓ ↓c␈ε#b)␈↓ α␈ε#Sa␈α␈me␈αa␈α␈s␈α(a␈α␈),␈αb␈α␈ut␈αu␈α␈se␈αthe␈αu␈α␈nits␈αd␈α␈i␈α↓g␈α␈it␈αof␈αthe␈ε0␈αp␈α␈ag␈α␈e␈ε#␈αn␈α␈u␈α␈m␈α␈ber.
␈β
e␈↓ ↓g␈ε#c)␈↓ α␈ε#Roll␈αa␈αd␈α␈ie␈αtha␈α␈t␈αis␈αi␈α↓n␈αthe␈αsha␈α␈pe␈αo␈α␈f␈αa␈αreg␈α␈ular␈αicos␈α␈ahe␈α␈dron␈α␈,␈αw␈α↓h␈α␈ose␈αt␈α␈we␈α␈n␈α␈t␈α␈y␈αf␈α↓a␈α␈ces␈αh␈α␈a␈α␈v␈α␈e
␈β∞␈↓ α␈ε#be␈α␈en␈αlab␈α␈eled␈αwith␈αthe␈αd␈α␈igits␈α
0␈α␈,␈αε0,␈α¬1,␈αε1,␈↓ ε.␈ε#.␈αε.␈αε.␈↓ ε[␈ε#,␈αε9␈α␈,␈αε9.␈α∩Use␈αthe␈αdig␈α␈i␈α↓t␈αth␈α␈at␈αap␈α␈pea␈α␈rs␈α
o␈α␈n␈αtop␈α␈,
␈β∞4␈↓ α␈ε#whe␈α␈n␈αt␈α␈he␈α
die␈αc␈α␈omes␈α
to␈α
rest.␈α_(A␈αfe␈α␈l␈α↓t␈α
tab␈α␈l␈α↓e␈α
with␈αa␈α
h␈α␈ard␈α
sur␈α␈f␈α↓a␈α␈ce␈α
i␈α↓s␈α
reco␈α␈mmen␈α␈ded␈α
fo␈α␈r
␈β∞[␈↓ α␈ε#rolling␈αd␈α␈ice.)
␈β∂β␈↓ ↓c␈ε#d)␈↓ α␈ε#Exp␈α␈ose␈α⊂a␈α∂geige␈α␈r␈α⊂cou␈α␈n␈α␈ter␈α⊂to␈α∂a␈α⊂so␈α␈urce␈α∂of␈α⊂rad␈α␈i␈α↓o␈α␈activ␈α␈i␈α↓t␈α␈y␈α∂for␈α⊂on␈α␈e␈α⊂min␈α}ute␈α⊂(sh␈α␈iel␈α↓d␈α␈ing
␈β∂+␈↓ α␈ε#y␈α␈o␈α␈urself)␈α
and␈αuse␈α
the␈α
u␈α␈nits␈α
digit␈α
of␈α
the␈α
resu␈α␈l␈α↓tin␈α␈g␈α
cou␈α␈n␈α␈t.␈α⊗Assu␈α␈me␈α
tha␈α␈t␈α∞th␈α␈e␈α
geige␈α␈r
␈β∂R␈↓ α␈ε#co␈α␈un␈α␈te␈α␈r␈αd␈α␈i␈α↓sp␈α␈la␈α␈ys␈αthe␈αn␈α␈u␈α␈m␈α␈b␈α␈er␈αo␈α␈f␈αcou␈α␈n␈α␈ts␈αi␈α↓n␈αd␈α␈ecima␈α␈l␈αno␈α␈tation␈α␈,␈αan␈α␈d␈αth␈α␈at␈αthe␈αcou␈α␈n␈α␈t␈αis
␈β∂z␈↓ α␈ε#initially␈αzero␈α␈.
␈β⊂"␈↓ ↓g␈ε#e)␈↓ α␈ε#Glan␈α␈ce␈αat␈αy␈α␈o␈α␈ur␈αwrist␈α␈w␈α␈atch␈α␈;␈α
an␈α␈d␈αif␈α
th␈α␈e␈αpo␈α␈si␈α↓t␈α␈i␈α↓o␈α␈n␈αof␈αthe␈αse␈α␈con␈α␈d-h␈α␈and␈αis␈α
b␈α␈et␈α␈w␈α␈een␈α6␈ε)n
␈β⊂I␈↓ α␈ε#an␈α␈d␈α6␈α␈(␈ε)␈α↓n␈ε#␈απ+␈αλ1)␈αsec␈α␈ond␈α␈s,␈αchoose␈αth␈α␈e␈αdigit␈ε)␈αn␈ε#.
␈β⊂q␈↓ ↓k␈ε#f)␈↓ α␈ε#Ask␈αa␈α
fri␈α↓e␈α␈nd␈αto␈α
think␈α
of␈αa␈αra␈α␈nd␈α␈om␈αd␈α␈i␈α↓g␈α␈it,␈αa␈α␈nd␈αu␈α␈se␈αth␈α␈e␈αdigit␈αh␈α␈e␈αna␈α␈mes.
␈β⊃→␈↓ ↓e␈ε#g)␈↓ α␈ε#Ask␈αa␈α␈n␈αen␈α␈em␈α␈y␈α
to␈αthin␈α␈k␈αof␈αa␈αra␈α␈nd␈α␈om␈αd␈α␈igit,␈αa␈α␈nd␈α
use␈αth␈α␈e␈αdigit␈αh␈α␈e␈αna␈α␈mes.
␈β∪(

␈β↓U␈↓ ↓H␈ε"3.1␈↓ ~␈ε"7
␈β↓\␈↓ λ<␈ε∞INT␈α↓R␈α␈ODU␈α↓CTION
␈βα%␈↓ ↓c␈ε#h)␈↓ α␈ε#Assu␈α␈me␈αth␈α␈at␈α1␈α␈0␈αh␈α␈orse␈α␈s␈αare␈α
en␈α␈te␈α␈red␈α
i␈α↓n␈α
a␈α
race␈α
an␈α␈d␈αt␈α␈hat␈α
y␈α␈ou␈α
k␈α␈no␈α␈w␈α
not␈α␈hing␈α
wha␈α␈tev␈α␈e␈α␈r
␈βαM␈↓ α␈ε#ab␈α␈ou␈α␈t␈α∞the␈α␈i␈α↓r␈α
qua␈α␈l␈α↓i|␈α␈cation␈α␈s.␈α↔Assi␈α↓g␈α␈n␈α∞t␈α␈o␈α∞th␈α␈ese␈α∞h␈α␈orses␈α
the␈α∞d␈α␈igits␈α∞0␈α∞t␈α␈o␈α∞9,␈α∞i␈α↓n␈α
arb␈α␈itrary
␈βαt␈↓ α␈ε#fash␈α␈ion,␈αan␈α␈d␈αa␈α␈$er␈αthe␈αra␈α␈ce␈αu␈α␈se␈αthe␈αwin␈α␈ner's␈αdig␈α␈i␈α↓t.
␈ββ%␈↓ ↓g␈ε32.␈↓ α␈ε#[␈ε)M2␈α␈2␈↓ α\␈ε#]␈α⊗In␈αa␈αra␈α␈nd␈α␈om␈αseq␈α␈uen␈α␈ce␈αof␈αa␈αm␈α␈i␈α↓llion␈αd␈α␈ecimal␈αd␈α␈i␈α↓g␈α␈i␈α↓ts,␈αwha␈α␈t␈α
is␈αth␈α␈e␈αpro␈α␈bab␈α␈il␈α↓it␈α␈y
␈ββM␈↓ ↓H␈ε#th␈α␈at␈αth␈α␈ere␈αare␈α
exa␈α␈ctly␈α10␈α␈0,000␈α
of␈αeac␈α␈h␈αpo␈α␈ssible␈αd␈α␈i␈α↓g␈α␈i␈α↓t?
␈ββ⎇␈↓ ↓g␈ε33.␈↓ α␈ε#[␈ε)10␈↓ α;␈ε#]␈α⊗Wha␈α␈t␈αn␈α␈u␈α␈m␈α␈be␈α␈r␈αf␈α↓o␈α␈ll␈α↓o␈α}w␈α↓s␈α1␈α␈010␈α␈10␈α␈101␈α␈0␈αin␈αth␈α␈e␈↓ π.␈ε#midd␈α␈l␈α↓e␈α␈-␈α↓s␈α␈qua␈α␈re␈αmeth␈α␈od␈α␈?
␈β∧.␈↓ ↓g␈ε34.␈↓ α␈ε#[␈ε)10␈↓ α;␈ε#]␈α⊗Wh␈α␈y␈απca␈α␈n't␈αλth␈α␈e␈απv␈α}alue␈απof␈↓ ¬!␈ε)X␈↓ ¬H␈ε#be␈απzero␈απwh␈α␈en␈απstep␈απK11␈απof␈απA␈α↓lg␈α␈orithm␈απK␈αλis␈απperfo␈α␈rmed␈α␈?
␈β∧V␈↓ ↓H␈ε#Wh␈α␈at␈αw␈α␈ou␈α␈l␈α↓d␈α
be␈αwro␈α␈ng␈αwith␈α
the␈αa␈α␈l␈α↓g␈α␈orithm␈αif␈↓ εR␈ε)X␈↓ ε|␈ε#cou␈α␈ld␈αb␈α␈e␈αzero?
␈β¬ε␈↓ ↓g␈ε35.␈↓ α␈ε#[␈ε)15␈↓ α;␈ε#]␈α⊗Ex␈α␈plain␈α
wh␈α␈y␈α␈,␈α∂in␈α
an␈α}y␈α
case␈α␈,␈α∂Algo␈α␈ri␈α↓t␈α␈hm␈α
K␈α∞sh␈α␈ou␈α␈ld␈α
not␈α
be␈α
ex␈α␈pe␈α␈cted␈α
to␈α
pro␈α}vide
␈β¬.␈↓ ↓H␈ε#\␈α␈i␈α↓n␈α␈|n␈α␈itely␈α∂m␈α␈an␈α␈y␈α␈"␈α∞rand␈α␈om␈α∞n␈α␈u␈α␈m␈α␈b␈α␈ers,␈α⊂in␈α∞the␈α∞sense␈α∞tha␈α␈t␈α∂(ev␈α}en␈α∞i␈α↓f␈α∞the␈α∞coin␈α␈ci␈α↓d␈α␈en␈α␈ce␈α∂g␈α␈iv␈α␈en
␈β¬U␈↓ ↓H␈ε#in␈α
T␈α⎇able␈α
1␈α∞h␈α␈ad␈α
no␈α␈t␈α∞occ␈α␈urred␈α␈)␈α∞on␈α␈e␈α∞k␈α␈no␈α}ws␈α∞in␈α∞a␈α␈dv␈α}a␈α␈nc␈α␈e␈α∞th␈α␈at␈α∞an␈α}y␈α
sequ␈α␈enc␈α␈e␈α∞ge␈α␈nera␈α␈ted␈α
by
␈β¬⎇␈↓ ↓H␈ε#Algo␈α␈rithm␈αK␈αwill␈αe␈α␈v␈α␈en␈α}tually␈αb␈α␈e␈αpe␈α␈ri␈α↓o␈α␈dic.
␈βε,␈↓ ↓;␈ε↓x
␈βε.␈↓ ↓g␈ε36.␈↓ α␈ε#[␈ε)M2␈α␈1␈↓ α\␈ε#]␈α⊗Su␈α␈pp␈α␈ose␈αth␈α␈at␈αw␈α␈e␈α
wa␈α␈n␈α␈t␈αto␈α
gen␈α␈erat␈α␈e␈αa␈αseq␈α␈ue␈α␈nce␈α
of␈↓ λ?␈ε#in␈α␈teg␈α␈ers␈↓ 	:␈ε)X␈↓ 	e␈ε#,␈↓ 	y␈ε)X␈↓ 
$␈ε#,␈↓ 
8␈ε)X␈↓ 
c␈ε#,␈↓ 
w␈ε#.␈αε.␈α¬.␈↓ #␈ε#,
␈βε9␈↓ 	V␈ε&0␈↓ 
∀␈ε&1␈↓ 
S␈ε&2
␈βεU␈↓ ↓H␈ε#in␈αthe␈αran␈α␈ge␈α
0␈ε7␈α∀␈↓ βR␈ε)X␈↓ ∧␈ε#<␈ε)␈α
m␈ε#␈α␈.␈α∀L␈α↓e␈α␈t␈↓ ¬2␈ε)f␈↓ ¬F␈ε#(␈ε)x␈ε#␈α␈)␈α
be␈αan␈α␈y␈αfun␈α␈ction␈αsu␈α␈ch␈α
t␈α␈hat␈α0␈ε7␈α∀␈ε)␈αx␈ε#␈α<␈ε)␈αm␈ε#␈α
imp␈α␈li␈α↓e␈α␈s
␈βεa␈↓ βm␈ε,n
␈βε⎇␈↓ ↓H␈ε#0␈ε7␈α
∀␈↓ α∂␈ε)f␈↓ α#␈ε#(␈ε)x␈ε#␈α␈)␈α<␈ε)␈αm␈ε#.␈α∩Co␈α␈nsid␈α␈er␈αa␈αseq␈α␈uen␈α␈ce␈αfo␈α␈rmed␈αby␈αthe␈αru␈α␈le␈↓ λ␈ε)X␈↓ λm␈ε#=␈↓ 	→␈ε)f␈↓ 	-␈ε#(␈↓ 	8␈ε)X␈↓ 	e␈ε#)␈α↓.␈α≠(Exa␈α␈mp␈α␈l␈α↓e␈α␈s
␈βπ	␈↓ λ(␈ε,n␈ε&+1␈↓ 	S␈ε,n
␈βπ%␈↓ ↓H␈ε#a␈α␈re␈αthe␈αm␈α␈i␈α↓d␈α␈dle-sq␈α␈ua␈α␈re␈αmeth␈α␈od␈αa␈α␈nd␈α
Al␈α↓g␈α␈orithm␈α
K.␈α↓)
␈βπS␈↓ ↓e␈ε#a)␈↓ α␈ε#Sh␈α␈o␈α␈w␈αλth␈α␈at␈αλthe␈απsequ␈α␈enc␈α␈e␈αλi␈α↓s␈αλu␈α␈lti␈α↓m␈α␈ately␈αλp␈α␈eriod␈α␈i␈α↓c␈α␈,␈α	i␈α↓n␈απthe␈απsense␈αλth␈α␈at␈αλth␈α␈ere␈αλex␈α␈ist␈αλn␈α␈u␈α␈m␈α␈ber␈α␈s
␈βπ{␈↓ α␈ε)∃␈ε#␈α∂an␈α␈d␈ε)␈α∞⊗␈ε#␈α∂for␈α∂wh␈α␈ich␈α∞the␈α∞v␈α}alu␈α␈es␈↓ ¬T␈ε)X␈↓ ¬␈␈ε#,␈↓ ε↔␈ε)X␈↓ εB␈ε#,␈↓ ε[␈ε#.␈αε.␈α¬.␈↓ ππ␈ε#,␈↓ π ␈ε)X␈↓ πM␈ε#,␈↓ πf␈ε#.␈αε.␈αε.␈↓ λ∩␈ε#,␈↓ λ+␈ε)X␈↓ 	9␈ε#are␈α∂d␈α␈istinct,␈α∂bu␈α␈t
␈βλπ␈↓ ¬o␈ε&0␈↓ ε3␈ε&1␈↓ π<␈ε,⊗␈↓ λG␈ε,⊗␈ε&+␈ε,∃␈ε:␈␈ε&␈α↓1
␈βλ#␈↓ α␈ε)X␈↓ αm␈ε#=␈↓ β_␈ε)X␈↓ βP␈ε#whe␈α␈n␈ε)␈αn␈ε7␈α	∃␈ε)␈α
⊗␈ε#.␈α∂Find␈α
th␈α␈e␈αma␈α␈xim␈α␈u␈α␈m␈αan␈α␈d␈α
minim␈α␈u␈α␈m␈αp␈α␈ossible␈α
v␈α}alu␈α␈es␈αof␈ε)␈α
⊗
␈βλ.␈↓ α(␈ε,n␈ε&␈α␈+␈ε,␈α↓∃␈↓ β3␈ε,n
␈βλJ␈↓ α␈ε#an␈α␈d␈ε)␈α∃␈ε#.
␈βλr␈↓ ↓c␈ε#b)␈↓ α␈ε#(R.␈α
W.␈↓ α⎇␈ε#F␈α↓lo␈α␈y␈α␈d.)␈α≠Sh␈α␈o␈α␈w␈αthat␈αth␈α␈ere␈αex␈α␈i␈α↓st␈α␈s␈α
a␈α␈n␈ε)␈αn␈ε#␈α>␈α0␈αsu␈α␈ch␈αth␈α␈at␈↓ 	¬␈ε)X␈↓ 	>␈ε#=␈↓ 	k␈ε)X␈↓ 
&␈ε#;␈α
an␈α␈d␈αthe
␈βλ⎇␈↓ 	!␈ε,n␈↓ 
ε␈ε&2␈ε,n
␈β	→␈↓ α␈ε#sma␈α␈l␈α↓lest␈αsu␈α␈ch␈α
v␈α}alue␈α
of␈ε)␈αn␈ε#␈αlies␈αin␈αth␈α␈e␈αran␈α␈ge␈ε)␈α
⊗␈ε7␈α
∀␈ε)␈α	n␈ε7␈α
∀␈ε)␈α
⊗␈ε#␈απ+␈ε)␈αλ∃␈ε#.␈α∂F␈α⎇urth␈α␈ermo␈α␈re␈αthe␈αv␈α⎇alue
␈β	A␈↓ α␈ε#of␈↓ α3␈ε)X␈↓ αl␈ε#is␈αun␈α␈iqu␈α␈e␈αi␈α↓n␈α
the␈αs␈α␈ense␈αth␈α␈at␈αif␈↓ ε∃␈ε)X␈↓ εL␈ε#=␈↓ εw␈ε)X␈↓ π=␈ε#and␈↓ π}␈ε)X␈↓ λ1␈ε#=␈↓ λ\␈ε)X␈↓ 	∪␈ε#,␈αthen␈↓ 	s␈ε)X␈↓ 
&␈ε#=␈↓ 
Q␈ε)X␈↓ 
␈␈ε#.
␈β	M␈↓ αN␈ε,n␈↓ ε1␈ε,n␈↓ π∩␈ε&2␈ε,n␈↓ λ~␈ε,r␈↓ λw␈ε&2␈↓ 	¬␈ε,r␈↓ 
∂␈ε,r␈↓ 
l␈ε,n
␈β	i␈↓ ↓g␈ε#c)␈↓ α␈ε#Use␈α
the␈α
ide␈α␈a␈α
of␈α∞p␈α␈art␈α
(b)␈α
to␈α
de␈α␈si␈α↓g␈α␈n␈α
an␈α
a␈α␈l␈α↓g␈α␈orithm␈α
th␈α␈at␈α
calcu␈α␈lates␈ε)␈α
⊗␈ε#␈α∞a␈α␈nd␈ε)␈α
∃␈ε#␈α∞fo␈α␈r␈α∞a␈α␈n␈α␈y
␈β
⊂␈↓ α␈ε#giv␈α␈e␈α␈n␈α
fu␈α␈nctio␈α␈n␈↓ βd␈ε)f␈↓ ∧↓␈ε#and␈α	an␈α}y␈α	giv␈α␈en␈↓ ¬T␈ε)X␈↓ ¬␈␈ε#,␈α
usin␈α␈g␈α
on␈α␈ly␈↓ π0␈ε)O␈↓ πJ␈ε#(␈ε)⊗␈ε#␈α¬+␈ε)␈α¬∃␈ε#␈α↓)␈α
ste␈α␈ps␈α
a␈α␈nd␈α	on␈α␈l␈α↓y␈α	a␈α	bou␈α␈nd␈α␈ed
␈β
≤␈↓ ¬p␈ε&0
␈β
8␈↓ α␈ε#n␈α␈u␈α␈m␈α␈b␈α␈er␈αof␈αmem␈α␈ory␈αloc␈α␈ation␈α␈s.
␈β
g␈↓ ↓;␈ε↓x
␈β
i␈↓ ↓g␈ε37.␈↓ α␈ε#[␈ε)M2␈α␈1␈↓ α\␈ε#]␈α⊗(R.␈α
P.␈↓ βa␈ε#Bren␈α␈t␈α␈,␈α
19␈α␈77.)␈α≠Let␈ε)␈α#␈ε#(␈ε)n␈ε#)␈αbe␈αthe␈αlea␈α␈st␈αpo␈α␈w␈α␈er␈αof␈α2␈αth␈α␈at␈αis␈αless␈αtha␈α␈n␈αo␈α␈r
␈β⊂␈↓ ↓H␈ε#e␈α␈qua␈α␈l␈αto␈ε)␈α
n␈ε#␈α↓;␈αth␈α␈u␈α␈s,␈αfor␈αex␈α␈amp␈α␈l␈α↓e␈α␈,␈ε)␈α#␈ε#␈α␈(␈α↓1␈α␈5)␈α	=␈α
8␈α
and␈ε)␈α
#␈ε#(␈ε)#␈ε#(␈ε)n␈ε#))␈α
=␈ε)␈α	#␈ε#(␈ε)n␈ε#).
␈β?␈↓ ↓e␈ε#a)␈↓ α␈ε#Sh␈α␈o␈α␈w␈αt␈α␈hat,␈αin␈α
term␈α␈s␈αof␈αt␈α␈he␈α
nota␈α␈tion␈α
in␈αe␈α␈xercise␈α
6,␈αth␈α␈ere␈αe␈α␈xists␈αa␈α␈n␈ε)␈α
n␈ε#␈α
>␈α
0␈α
su␈α␈ch␈α
tha␈α␈t
␈βg␈↓ α␈ε)X␈↓ αC␈ε#=␈↓ αn␈ε)X␈↓ βb␈ε#.␈α⊂Find␈α
a␈αform␈α␈u␈α␈l␈α↓a␈α
tha␈α␈t␈αe␈α␈xp␈α␈resses␈αthe␈αlea␈α␈st␈αsuch␈ε)␈α
n␈ε#␈αin␈αterm␈α␈s␈αof␈ε)␈α⊗␈ε#␈αa␈α␈nd
␈βr␈↓ α(␈ε,n
␈βs␈↓ β	␈ε,#␈ε&␈α↓(␈ε,␈α␈n␈ε&)␈ε:␈␈ε&1
␈β∞␈↓ α␈ε)∃␈ε#.
␈β6␈↓ ↓c␈ε#b)␈↓ α␈ε#App␈α␈ly␈α
this␈α
resu␈α␈lt␈α
to␈α
de␈α␈si␈α↓g␈α␈n␈α
an␈α	algo␈α␈ri␈α↓th␈α␈m␈α
th␈α␈at␈α
can␈α	be␈α
u␈α␈sed␈α
in␈α	con␈α␈jun␈α␈ction␈α
with␈α
a␈α␈n␈α␈y
␈β]␈↓ α␈ε#ran␈α␈do␈α␈m␈αn␈α}um␈α}ber␈αgen␈α␈era␈α␈tor␈αof␈αth␈α␈e␈αt␈α␈ype␈↓ ε?␈ε)X␈↓ π∨␈ε#=␈↓ πJ␈ε)f␈↓ π]␈ε#(␈↓ πi␈ε)X␈↓ λ⊗␈ε#),␈αto␈αprev␈α}en␈α␈t␈αit␈αfro␈α␈m␈αc␈α␈y␈α␈cling
␈βi␈↓ εZ␈ε,n␈ε&+␈α↓1␈↓ λ∧␈ε,n
␈β
¬␈↓ α␈ε#ind␈α␈e|n␈α␈itely.␈α⊗Y␈α⎇o␈α␈ur␈α
algo␈α␈ri␈α↓th␈α␈m␈α
sho␈α␈uld␈α
ca␈α␈lculate␈α
th␈α␈e␈α
per␈α␈i␈α↓o␈α␈d␈α
leng␈α␈th␈ε)␈α
∃␈ε#␈α↓,␈α∞a␈α␈nd␈α
it␈α
sho␈α␈uld
␈β
-␈↓ α␈ε#us␈α␈e␈α
o␈α␈nly␈αa␈αsm␈α␈all␈α
a␈α␈mou␈α␈n␈α␈t␈αof␈αmem␈α␈ory␈αsp␈α␈ace←y␈α}ou␈αm␈α␈u␈α␈st␈αnot␈αsimp␈α␈ly␈αstore␈αa␈α␈l␈α↓l␈αof␈αthe
␈β
T␈↓ α␈ε#co␈α␈mpu␈α␈ted␈αse␈α␈que␈α␈nce␈αv␈α⎇alue␈α␈s!
␈β∞¬␈↓ ↓g␈ε38.␈↓ α␈ε#[␈ε)28␈↓ α;␈ε#]␈α⊗M␈α␈ak␈α␈e␈απa␈αλc␈α␈omp␈α␈l␈α↓e␈α␈te␈αλex␈α␈amin␈α␈ation␈απof␈αλth␈α␈e␈αλmid␈α␈dle-squ␈α␈are␈απmeth␈α␈od␈απi␈α↓n␈απth␈α␈e␈αλca␈α␈se␈αλof␈αλt␈α␈w␈α␈o␈α␈-
␈β∞-␈↓ ↓H␈ε#d␈α␈igit␈α
d␈α␈ecimal␈α
n␈α}um␈α␈b␈α␈ers.␈α∀(a)␈α	W␈α}e␈α	migh␈α␈t␈α	start␈α	the␈α	proc␈α␈ess␈α
o␈α␈ut␈α
with␈α	an␈α}y␈α
o␈α␈f␈α
th␈α␈e␈α
10␈α␈0␈α
p␈α␈ossib␈α␈l␈α↓e
␈β∞T␈↓ ↓H␈ε#v␈α⎇alues␈α
00␈α␈,␈α01␈α␈,␈↓ β∀␈ε#.␈αε.␈αε.␈↓ βA␈ε#,␈α
99.␈α∂Ho␈α}w␈αma␈α␈n␈α␈y␈α
of␈α
the␈α␈se␈αv␈α⎇alue␈α␈s␈αlead␈α
u␈α␈ltimately␈α
to␈α
th␈α␈e␈αre␈α␈pea␈α␈ti␈α↓n␈α␈g␈α
cy␈α␈c␈α␈l␈α↓e
␈β∞|␈↓ ↓H␈ε#0␈α␈0,␈α00,␈↓ α3␈ε#.␈αε.␈α¬.␈↓ α←␈ε#?␈α∂[␈ε0Exam␈α␈ple:␈ε#␈αSta␈α␈rting␈αwith␈α
43,␈αw␈α␈e␈αob␈α␈tain␈αth␈α␈e␈αseq␈α␈uen␈α␈ce␈α4␈α␈3,␈α84,␈α05␈α␈,␈α0␈α␈2,␈α00,␈α00␈α␈,
␈β∂#␈↓ ↓H␈ε#0␈α␈0,␈↓ ↓{␈ε#.␈αε.␈αε.␈↓ α(␈ε#.]␈α⊂(b␈α␈)␈α	Ho␈α␈w␈α	m␈α␈an␈α}y␈α	p␈α␈ossib␈α␈l␈α↓e␈αλ|n␈α␈al␈α	c␈α␈y␈α␈cles␈α	a␈α␈re␈α	th␈α␈ere?␈α
H␈α↓o␈α}w␈α	lon␈α␈g␈α	is␈αλthe␈αλl␈α↓o␈α␈ng␈α␈est␈α	c␈α␈y␈α␈cle?␈α∂(␈α↓c␈α␈)
␈β∂K␈↓ ↓H␈ε#Wh␈α␈at␈αstar␈α␈ti␈α↓n␈α␈g␈αv␈α⎇alue␈αo␈α␈r␈αv␈α}a␈α␈l␈α↓u␈α␈es␈αwill␈α
g␈α␈iv␈α␈e␈αth␈α␈e␈αlarg␈α␈est␈αn␈α␈u␈α␈m␈α␈b␈α␈er␈αof␈αd␈α␈i␈α↓s␈α␈ti␈α↓n␈α␈ct␈αelem␈α␈en␈α␈ts␈αb␈α␈efore
␈β∂s␈↓ ↓H␈ε#th␈α␈e␈αseq␈α␈uen␈α␈ce␈αrep␈α␈eats?
␈β⊂#␈↓ ↓g␈ε39.␈↓ α␈ε#[␈ε)M1␈α␈4␈↓ α\␈ε#]␈α⊗Pro␈α␈v␈α␈e␈α	tha␈α␈t␈α
the␈α	midd␈α␈le-squ␈α␈are␈α	meth␈α␈od␈α	using␈α	2␈ε)n␈ε#-dig␈α␈i␈α↓t␈α	n␈α␈u␈α␈m␈α␈ber␈α␈s␈α
to␈α	the␈α	base␈ε)␈α	b
␈β⊂K␈↓ ↓H␈ε#h␈α␈as␈α∩th␈α␈e␈α∩fo␈α␈l␈α↓lo␈α␈win␈α␈g␈α∩d␈α␈i␈α↓sa␈α␈dv␈α⎇an␈α␈ta␈α␈ge:␈α→If␈α∩th␈α␈e␈α∩se␈α␈que␈α␈nce␈α⊃i␈α↓n␈α␈clud␈α␈es␈α∩a␈α␈n␈α␈y␈α⊃n␈α␈u␈α␈m␈α␈ber␈α⊃whose␈α⊃mos␈α␈t
␈β⊂r␈↓ ↓H␈ε#sig␈α␈ni|ca␈α␈n␈α␈t␈ε)␈αn␈ε#␈αd␈α␈igits␈αare␈αzero␈α␈,␈αth␈α␈e␈αsucc␈α␈eedin␈α␈g␈αn␈α␈u␈α␈m␈α␈be␈α␈rs␈αwill␈αg␈α␈et␈αsmaller␈αan␈α␈d␈αsma␈α␈l␈α↓ler␈αu␈α␈n␈α␈til
␈β⊃~␈↓ ↓H␈ε#z␈α␈ero␈αoc␈α␈curs␈αre␈α␈pea␈α␈tedly␈α␈.
␈β∪(

␈β↓U␈↓ ↓H␈ε"8␈↓ 
}␈ε"3.1
␈β↓\␈↓ α=␈ε∞RANDOM␈α
NU␈α↓MB␈α␈E␈α↓RS
␈βα%␈↓ ↓V␈ε310.␈↓ α␈ε#[␈ε)M1␈α␈6␈↓ α\␈ε#]␈α⊗Und␈α␈er␈αthe␈αa␈α␈ssum␈α␈ption␈α␈s␈αof␈αthe␈α
prece␈α␈ding␈α
exe␈α␈rcise,␈αwh␈α␈at␈αca␈α␈n␈αy␈α␈o␈α␈u␈αsa␈α␈y␈α
ab␈α␈ou␈α␈t
␈βαM␈↓ ↓H␈ε#th␈α␈e␈α∞sequ␈α␈en␈α␈ce␈α∞of␈α∞n␈α␈u␈α␈m␈α␈be␈α␈rs␈α∂fo␈α␈l␈α↓lo␈α␈win␈α␈g␈↓ ¬S␈ε)X␈↓ ε↓␈ε#if␈α∞the␈ε0␈α∞lea␈α␈st␈ε#␈α∂sig␈α␈ni|c␈α␈an␈α␈t␈ε)␈α∞n␈ε#␈α∞digits␈α∞of␈↓ 	|␈ε)X␈↓ 
*␈ε#a␈α␈re␈α∞zero␈α␈?
␈βαt␈↓ ↓H␈ε#Wh␈α␈at␈αif␈αth␈α␈e␈αleast␈αsign␈α␈i|ca␈α␈n␈α␈t␈ε)␈αn␈ε#␈αλ+␈απ1␈αdig␈α␈i␈α↓ts␈αa␈α␈re␈αzero␈α␈?
␈ββ%␈↓ ↓;␈ε↓x
␈ββ'␈↓ ↓V␈ε311.␈↓ α␈ε#[␈ε)M2␈α␈6␈↓ α\␈ε#]␈α⊗Con␈α␈si␈α↓d␈α␈er␈α⊃seq␈α␈uen␈α␈ces␈α⊃o␈α␈f␈α∩ra␈α␈nd␈α␈om␈α⊃n␈α}um␈α␈b␈α␈er␈α⊃ge␈α␈nera␈α␈tors␈α⊃h␈α␈a␈α␈vin␈α␈g␈α⊃the␈α⊃fo␈α␈rm␈α⊃de␈α␈-
␈ββN␈↓ ↓H␈ε#sc␈α␈ri␈α↓b␈α␈ed␈α∞in␈α∂e␈α␈xerc␈α␈i␈α↓se␈α∞6.␈α~If␈α∞we␈α∞ch␈α␈o␈α↓ose␈↓ ¬a␈ε)f␈↓ ¬u␈ε#(␈ε)x␈ε#␈α␈)␈α∂an␈α␈d␈↓ εp␈ε)X␈↓ π*␈ε#at␈α∞ran␈α␈do␈α␈m,␈α⊂i.␈α↓e␈α␈.␈α↓,␈α∂i␈α↓f␈α∞we␈α∞assu␈α␈me␈α∞tha␈α␈t
␈ββZ␈↓ π␈ε&0
␈ββp␈↓ β≤␈ε,m
␈ββv␈↓ ↓H␈ε#e␈α␈ach␈α∞of␈α∞the␈↓ α}␈ε)m␈↓ βD␈ε#p␈α␈ossib␈α␈l␈α↓e␈α∞fun␈α␈ction␈α␈s␈↓ ¬W␈ε)f␈↓ ¬k␈ε#(␈ε)x␈ε#␈α␈)␈α∂is␈α∂e␈α␈qua␈α␈l␈α↓ly␈α∞p␈α␈roba␈α␈ble␈α∞and␈α∞th␈α␈at␈α∞each␈α∞o␈α␈f␈α∂th␈α␈e␈ε)␈α∂m
␈β∧≡␈↓ ↓H␈ε#p␈α␈ossib␈α␈l␈α↓e␈α	v␈α}alu␈α␈es␈α
of␈↓ βI␈ε)X␈↓ β}␈ε#is␈α
eq␈α␈ua␈α␈l␈α↓ly␈α	pro␈α␈bab␈α␈le,␈α
what␈α	i␈α↓s␈α	the␈α	pro␈α␈bab␈α␈il␈α↓it␈α␈y␈α	tha␈α␈t␈α
th␈α␈e␈α
seq␈α␈uen␈α␈ce␈α
will
␈β∧)␈↓ βe␈ε&0
␈β∧E␈↓ ↓H␈ε#e␈α␈v␈α␈en␈α}tually␈α
d␈α␈ege␈α␈nera␈α␈te␈α
in␈α␈to␈αa␈α
cy␈α}cl␈α↓e␈αof␈α
leng␈α␈th␈ε)␈α
∃␈ε#␈α=␈α
1?␈α≥(␈ε0No␈α␈te:␈ε#␈α∂The␈αassum␈α␈ption␈α␈s␈α
of␈α
th␈α␈is
␈β∧m␈↓ ↓H␈ε#p␈α␈rob␈α␈lem␈αg␈α␈i␈α↓v␈α}e␈αa␈αna␈α␈tura␈α␈l␈αw␈α␈a␈α␈y␈αt␈α␈o␈αth␈α␈i␈α↓n␈α␈k␈αof␈αa␈α\ra␈α␈nd␈α␈om"␈αran␈α␈do␈α␈m␈αn␈α}um␈α␈b␈α␈er␈αg␈α␈ene␈α␈rator␈αof␈αth␈α␈is
␈β¬∀␈↓ ↓H␈ε#t␈α␈y␈α␈pe.␈α∀A␈α
me␈α␈tho␈α␈d␈α
su␈α␈ch␈αas␈α
Algo␈α␈ri␈α↓th␈α␈m␈α
K␈αma␈α␈y␈αbe␈α
e␈α␈xp␈α␈ected␈αto␈αbeh␈α␈a␈α␈v␈α␈e␈αsome␈α␈w␈α↓h␈α␈at␈αl␈α↓ik␈α␈e␈αthe
␈β¬<␈↓ ↓H␈ε#g␈α␈ene␈α␈rator␈αλcon␈α␈sidere␈α␈d␈α	h␈α␈ere;␈α	the␈αλan␈α␈sw␈α␈er␈α	to␈αλthis␈αλpro␈α␈blem␈αλgiv␈α␈es␈αλa␈α	m␈α␈easu␈α␈re␈α	o␈α␈f␈α	ho␈α}w␈α	\c␈α␈olossal"
␈β¬d␈↓ ↓H␈ε#th␈α␈e␈αco␈α␈i␈α↓n␈α␈ciden␈α␈ce␈αo␈α␈f␈αT␈α⎇ab␈α␈le␈α1␈αrea␈α␈l␈α↓ly␈αis.)
␈βε∀␈↓ ↓;␈ε↓x
␈βε⊗␈↓ ↓V␈ε312.␈↓ α␈ε#[␈ε)M3␈α␈1␈↓ α\␈ε#]␈α⊗Und␈α␈er␈αλth␈α␈e␈αλas␈α␈sump␈α␈tions␈απof␈αλth␈α␈e␈αλp␈α␈reced␈α␈ing␈απexe␈α␈rcise,␈α	wh␈α␈at␈αλis␈αλth␈α␈e␈αλa␈α␈v␈α}erag␈α␈e␈αλlen␈α␈gth
␈βε>␈↓ ↓H␈ε#o␈α␈f␈αth␈α␈e␈α
|n␈α␈al␈αc␈α␈y␈α␈cle?␈α∞W␈α↓h␈α␈at␈α
is␈αth␈α␈e␈α
a␈α␈v␈α␈e␈α␈rage␈α
len␈α␈gth␈α
o␈α␈f␈αth␈α␈e␈α
sequ␈α␈enc␈α␈e␈αb␈α␈efore␈α
it␈α
beg␈α␈ins␈α
to␈α
cy␈α␈c␈α␈l␈α↓e␈α␈?
␈βεe␈↓ ↓H␈ε#(In␈αλthe␈α	n␈α␈ota␈α␈ti␈α↓o␈α␈n␈α	o␈α␈f␈α
e␈α␈xerc␈α␈i␈α↓se␈αλ6,␈α
w␈α␈e␈α	wish␈α	to␈αλexa␈α␈mine␈α	t␈α␈he␈α	a␈α␈v␈α}erag␈α␈e␈α	v␈α}a␈α␈l␈α↓u␈α␈es␈α	of␈ε)␈α	∃␈ε#␈α	an␈α␈d␈α	of␈ε)␈α	⊗␈ε#␈αβ+␈ε)␈α∧∃␈ε#.)
␈βπ_␈↓ ↓V␈ε313.␈↓ α␈ε#[␈ε)M4␈α␈2␈↓ α\␈ε#]␈α⊗If␈↓ β≤␈ε)f␈↓ β/␈ε#(␈ε)x␈ε#)␈α
is␈α
cho␈α␈sen␈α
a␈α␈t␈α
ran␈α␈dom␈α	i␈α↓n␈α	the␈α
se␈α␈nse␈α
o␈α␈f␈αe␈α␈xerc␈α␈i␈α↓se␈α	11,␈α
what␈α
is␈α
th␈α␈e␈α
a␈α␈v␈α␈e␈α␈rage
␈βπ?␈↓ ↓H␈ε#len␈α␈gth␈α
of␈α
the␈ε0␈α
lon␈α␈gest␈ε#␈α
cy␈α␈cle␈α
ob␈α␈taina␈α␈ble␈α
by␈α
v␈α}ar␈α␈ying␈α
th␈α␈e␈α∞sta␈α␈rti␈α↓n␈α␈g␈α
v␈α}alu␈α␈e␈↓ 	?␈ε)X␈↓ 	i␈ε#?␈α≡(␈ε0␈α↓N␈α␈ote:␈ε#␈α⊂W␈α}e
␈βπK␈↓ 	Z␈ε&0
␈βπg␈↓ ↓H␈ε#h␈α␈a␈α␈v␈α␈e␈α⊂alrea␈α␈dy␈α⊂con␈α␈sidere␈α␈d␈α⊃th␈α␈e␈α⊃a␈α␈na␈α␈l␈α↓o␈α␈gou␈α␈s␈α⊃p␈α␈rob␈α␈l␈α↓e␈α␈m␈α⊃in␈α⊂the␈α⊂case␈α⊂tha␈α␈t␈↓ 	(␈ε)f␈↓ 	<␈ε#(␈ε)x␈ε#␈α␈)␈α⊃is␈α⊃a␈α⊂rand␈α␈om
␈βλ∞␈↓ ↓H␈ε#p␈α␈erm␈α␈u␈α␈tation␈α␈;␈αs␈α␈ee␈αex␈α␈ercise␈α1.3.3↑␈α␈23.)
␈βλA␈↓ ↓V␈ε314.␈↓ α␈ε#[␈ε)M3␈α␈8␈↓ α\␈ε#]␈α⊗If␈↓ β≤␈ε)f␈↓ β/␈ε#(␈ε)x␈ε#)␈α
is␈α
cho␈α␈sen␈α
a␈α␈t␈α
ran␈α␈dom␈α	i␈α↓n␈α	the␈α
se␈α␈nse␈α
o␈α␈f␈αe␈α␈xerc␈α␈i␈α↓se␈α	11,␈α
what␈α
is␈α
th␈α␈e␈α
a␈α␈v␈α␈e␈α␈rage
␈βλh␈↓ ↓H␈ε#n␈α}um␈α␈b␈α␈er␈αof␈αdistinct␈α|n␈α␈al␈αcy␈α␈cles␈αob␈α␈taina␈α␈ble␈αby␈αv␈α}a␈α␈rying␈αth␈α␈e␈αstarting␈αv␈α⎇alue?␈α→[␈α↓Cf.␈αe␈α␈xerc␈α␈i␈α↓se
␈β	⊂␈↓ ↓H␈ε#8␈α␈(b).]
␈β	B␈↓ ↓V␈ε315.␈↓ α␈ε#[␈ε)M1␈α␈5␈↓ α\␈ε#]␈α⊗If␈↓ β≡␈ε)f␈↓ β1␈ε#(␈ε)x␈ε#)␈αis␈αcho␈α␈sen␈αa␈α␈t␈α
r␈α␈and␈α␈om␈αin␈αthe␈αsen␈α␈se␈αof␈αex␈α␈ercise␈α1␈α␈1,␈α
wh␈α␈at␈αis␈αthe␈αp␈α␈rob␈α␈-
␈β	j␈↓ ↓H␈ε#a␈α␈bili␈α↓t␈α␈y␈α
tha␈α␈t␈αnon␈α␈e␈αof␈αth␈α␈e␈α|n␈α␈al␈αcy␈α␈c␈α␈l␈α↓e␈α␈s␈αh␈α␈as␈αlen␈α␈gth␈α
1,␈αregar␈α␈dless␈αof␈αth␈α␈e␈αcho␈α␈ice␈αof␈↓ 
~␈ε)X␈↓ 
E␈ε#?
␈β	v␈↓ 
5␈ε&0
␈β
≤␈↓ ↓V␈ε316.␈↓ α␈ε#[␈ε)15␈↓ α;␈ε#]␈α⊗A␈αsequ␈α␈enc␈α␈e␈αg␈α␈ener␈α␈ated␈αas␈αin␈αexerc␈α␈i␈α↓se␈α6␈αm␈α␈us␈α␈t␈αb␈α␈egin␈αto␈αrepea␈α␈t␈αa␈α␈$er␈αa␈α␈t␈αmo␈α␈st␈ε)␈αm
␈β
D␈↓ ↓H␈ε#v␈α⎇alues␈α
ha␈α␈v␈α}e␈αbe␈α␈en␈αg␈α␈ene␈α␈rated␈α␈.␈α∂Su␈α␈pp␈α␈ose␈αw␈α␈e␈αg␈α␈ene␈α␈ralize␈αth␈α␈e␈αmeth␈α␈od␈α
so␈αth␈α␈at␈↓ 	W␈ε)X␈↓ 
8␈ε#d␈α␈epe␈α␈nd␈α␈s
␈β
P␈↓ 	s␈ε,n␈ε&␈α␈+␈α↓1
␈β
l␈↓ ↓H␈ε#o␈α␈n␈↓ ↓v␈ε)X␈↓ αW␈ε#as␈αw␈α␈ell␈αa␈α␈s␈αo␈α␈n␈↓ ∧≠␈ε)X␈↓ ∧I␈ε#;␈αforma␈α␈l␈α↓ly␈α␈,␈αlet␈↓ ε≠␈ε)f␈↓ ε/␈ε#(␈ε)x␈ε#,␈↓ ε[␈ε)y␈↓ εm␈ε#)␈αbe␈αa␈αfu␈α␈nction␈α
such␈α
tha␈α␈t␈↓ 	d␈ε#0␈ε7␈α	∀␈ε)␈α	x␈ε#,␈↓ 
I␈ε)y␈↓ 
d␈ε#<␈ε)␈α
m
␈β
w␈↓ α∩␈ε,n␈ε:␈α␈␈␈ε&␈α↓1␈↓ ∧7␈ε,n
␈β∪␈↓ ↓H␈ε#imp␈α␈li␈α↓e␈α␈s␈α⊃0␈ε7␈α∪∀␈↓ β↔␈ε)f␈↓ β+␈ε#(␈ε)x␈ε#␈α␈,␈↓ βW␈ε)y␈↓ βi␈ε#)␈α∪<␈ε)␈α∪m␈ε#.␈α!The␈α⊂sequ␈α␈enc␈α␈e␈α⊃i␈α↓s␈α⊃c␈α␈ons␈α␈tructe␈α␈d␈α⊃by␈α⊂selectin␈α␈g␈↓ 	␈␈ε)X␈↓ 
;␈ε#an␈α␈d␈↓ α␈ε)X
␈β∨␈↓ 
≠␈ε&0␈↓ ≥␈ε&1
␈β;␈↓ ↓H␈ε#a␈α␈rbitrar␈α␈i␈α↓ly,␈αan␈α␈d␈αth␈α␈en␈αlettin␈α␈g
␈β
␈↓ ∧#␈ε)X␈↓ ¬β␈ε#=␈↓ ¬-␈ε)f␈↓ ¬A␈ε#(␈↓ ¬L␈ε)X␈↓ ¬z␈ε#,␈↓ ελ␈ε)X␈↓ ε↑␈ε#),␈↓ π;␈ε#for␈↓ πo␈ε)n␈ε#␈α	>␈α
0␈α␈.
␈β⊗␈↓ ∧?␈ε,n␈ε&+1␈↓ ¬g␈ε,n␈↓ ε$␈ε,n␈ε:␈␈ε&1
␈βY␈↓ ↓H␈ε#Wh␈α␈at␈αis␈αthe␈αma␈α␈xim␈α␈u␈α␈m␈αpe␈α␈ri␈α↓o␈α␈d␈αco␈α␈nce␈α␈i␈α↓v␈α⎇ably␈α
attain␈α␈able␈αin␈αth␈α␈is␈αcase?
␈β
␈↓ ↓V␈ε317.␈↓ α␈ε#[␈ε)10␈↓ α;␈ε#]␈α⊗Ge␈α␈nera␈α␈l␈α↓ize␈α
th␈α␈e␈α
situa␈α␈ti␈α↓o␈α␈n␈α
in␈α
th␈α␈e␈α
pre␈α␈viou␈α␈s␈α
exerc␈α␈i␈α↓se␈α
s␈α␈o␈α
tha␈α␈t␈↓ 	$␈ε)X␈↓ 
λ␈ε#d␈α␈ep␈α␈end␈α␈s␈α
on
␈β
↔␈↓ 	@␈ε,n␈ε&+1
␈β
3␈↓ ↓H␈ε#th␈α␈e␈αpr␈α␈eced␈α␈i␈α↓n␈α␈g␈↓ β↔␈ε)k␈↓ β4␈ε#v␈α}alue␈α␈s␈αof␈αthe␈αse␈α␈que␈α␈nce.
␈β
f␈↓ ↓V␈ε318.␈↓ α␈ε#[␈ε)M2␈α␈0␈↓ α\␈ε#]␈α⊗In␈α␈v␈α␈e␈α␈n␈α␈t␈α
a␈αmeth␈α␈od␈α
a␈α␈na␈α␈l␈α↓o␈α␈gou␈α␈s␈α
to␈α
th␈α␈at␈α
o␈α␈f␈α
exe␈α␈rcise␈α
7␈α
fo␈α␈r␈α
|n␈α␈ding␈αcy␈α␈cles␈αi␈α↓n␈αthe
␈β∞
␈↓ ↓H␈ε#g␈α␈ene␈α␈ral␈αform␈αof␈αra␈α␈nd␈α␈om␈αn␈α}um␈α␈b␈α␈er␈αgen␈α␈era␈α␈tor␈αdiscu␈α␈ssed␈α
i␈α↓n␈α
exe␈α␈rcise␈α17.
␈β∞@␈↓ ↓V␈ε319.␈↓ α␈ε#[␈ε)M4␈α␈8␈↓ α\␈ε#]␈α⊗So␈α␈l␈α↓v␈α}e␈αλth␈α␈e␈αλpr␈α␈oblem␈α␈s␈αλof␈αλex␈α␈ercises␈απ11␈αλth␈α␈rou␈α␈gh␈απ15␈απfor␈αλth␈α␈e␈αλmo␈α␈re␈αλge␈α␈nera␈α␈l␈αλcase␈απtha␈α␈t
␈β∞c␈↓ 

␈ε-k
␈β∞i␈↓ 	r␈ε,m
␈β∞o␈↓ ↓H␈ε)X␈↓ α*␈ε#d␈α␈epe␈α␈nd␈α␈s␈α
o␈α␈n␈αthe␈αp␈α␈reced␈α␈ing␈↓ ¬,␈ε)k␈↓ ¬K␈ε#v␈α⎇alue␈α␈s␈α
o␈α␈f␈α
th␈α␈e␈αsequ␈α␈enc␈α␈e;␈α
each␈αof␈αthe␈↓ 	U␈ε)m␈↓ 
'␈ε#fun␈α␈ction␈α␈s
␈β∞z␈↓ ↓c␈ε,n␈ε&+1
␈β∂⊗␈↓ ↓H␈ε)f␈↓ ↓[␈ε#(␈↓ ↓f␈ε)x␈↓ αλ␈ε#,␈↓ α↔␈ε#.␈αε.␈αε.␈↓ αC␈ε#,␈↓ αR␈ε)x␈↓ αu␈ε#)␈α∞is␈α∞to␈α∞be␈α∞c␈α␈onsid␈α␈ered␈α∞e␈α␈qu␈α␈all␈α↓y␈α
pro␈α␈bab␈α␈le.␈α (␈ε0No␈α␈te:␈ε#␈α⊃T␈α↓h␈α␈e␈α∞n␈α␈u␈α␈m␈α␈b␈α␈er␈α∞of␈α∞fun␈α␈ction␈α␈s
␈β∂"␈↓ ↓y␈ε&1␈↓ αe␈ε,k
␈β∂>␈↓ ↓H␈ε#th␈α␈at␈αy␈α␈i␈α↓e␈α␈l␈α↓d␈α
the␈ε0␈αm␈α␈axim␈α␈u␈α␈m␈ε#␈αp␈α␈eriod␈αis␈αan␈α␈alyz␈α␈ed␈αin␈αex␈α␈ercise␈α2␈α␈.␈α↓3␈α␈.4.2↑2␈α␈3.)
␈β∪(/FONT#1=cmathx[XGP,SYS]=xx/FONT#14=cmsc9[XGP,SYS]=ABCDEIMNORSTUU/FONT#32=cmsss8[XGP,SYS]=,.AKLSTabcdefghiklmnoprstuvwxyy/FONT#34=cmr10[XGP,SYS]=!"$'()+,-./0123456789:;<=>?ABCDEFGHIJKLMNOPRSTUVWY[\]↑←abcdefghijklmnopqrstuvwxyz{|⎇}␈␈/FONT#35=cmr9[XGP,SYS]=!"$'()+,-.0123456789:;<=>?ABCEFGHIKLMOPRSTUWY[\]↑←abcdefghijklmnopqrstuvwxyz||/FONT#36=cmr8[XGP,SYS]=.01234568:ABCDEFGHIKLMNORSTUYY/FONT#37=cmr7[XGP,SYS]=0125899/FONT#38=cmr6[XGP,SYS]=()+0122/FONT#40=cmi10[XGP,SYS]=XYZZ/FONT#41=cmi9[XGP,SYS]=∃⊗#01234568MOXYbfkmnxyy/FONT#44=cmi6[XGP,SYS]=∃⊗#kmnrr/FONT#45=cmi5[XGP,SYS]=kk/FONT#46=cmsc10[XGP,SYS]=BEMRSUU/FONT#47=cms10[XGP,SYS]="'-.CDJMNRS\abcdefghiklmnopqrstuwyzz/FONT#48=cms9[XGP,SYS]=:ENaegilmnopstuxx/FONT#50=cmb10[XGP,SYS]=.0123456789AKghilmortt/FONT#51=cmb9[XGP,SYS]=.01234567899/FONT#54=cmsy10[XGP,SYS]=α∃ bc⎇⎇/FONT#55=cmsy9[XGP,SYS]=∀∃∃/FONT#58=cmsy6[XGP,SYS]=/FONT#60=cmtitl[XGP,SYS]=ABDEMNORSUU/FONT#61=cmssb[XGP,SYS]=.13CDEINORSTUXabell/FONT#62=cmss12[XGP,SYS]=ACEHPRTT/FONT#63=cmss8[XGP,SYS]=()125679AEGHJMNOUVWY←←